AQA FP2 - Proof by induction

Hello, I'm having trouble with writing a small statement once you have completed a proof and shown the result is true for n=k then n=k+1.

Would the statement 'By mathematical induction, the result n=k+1 has been proven for all real numbers and therefore, n=k must hold for all real numbers aswell', not forgetting to prove the base case (i.e when n=1 or the lowest value for n).

Thanks!

Reply 1

M^2012

I think I wrote: "True for n=1 and n=k+1, therefore true for all positive integers n by induction"
Although I didn't get 100 UMS, so I might not have got that mark :P

Reply 2

ztibor

10

Original post by amish123

Hello, I'm having trouble with writing a small statement once you have completed a proof and shown the result is true for n=k then n=k+1.

Would the statement 'By mathematical induction, the result n=k+1 has been proven for all real numbers and therefore, n=k must hold for all real numbers aswell', not forgetting to prove the base case (i.e when n=1 or the lowest value for n).

Thanks!

This would not.
THe set of natural numbers is countable infinitive
(This is a set of discrete elements. Every elements have a well defined successor of S for 1 S(1)=1+1=2 ... for n S(n)=n+1)

This does not hold for real numbers
The set of reals is uncountable infinite. An element has no successor.

Reply 3

Indeterminate

3

Original post by amish123

Hello, I'm having trouble with writing a small statement once you have completed a proof and shown the result is true for n=k then n=k+1.

Would the statement 'By mathematical induction, the result n=k+1 has been proven for all real numbers and therefore, n=k must hold for all real numbers aswell', not forgetting to prove the base case (i.e when n=1 or the lowest value for n).

Thanks!

When I did FP1 2 years back (time really does fly), I devised the following, which can be used regardless of whether you're proving the result over the reals, integers, etc.

"The result holds for n=k+1 as a consequence of the assumption that it holds for n=k. Hence, since it is true for n=1, it is true for all positive integers

n \geq 1

by induction "

1 is usually your base case, but you should obviously change the final line if it's different.

(edited 11 years ago)

Reply 4

Smaug123

15

Indeterminate's is absolutely fine; as my two cents, for the exam I wrote:
The proposition is true for the case n=1: <proof>
Assuming the proposition's truth for n=k: <working…> and hence the proposition is true for n=k+1.
Hence by the Principle of Mathematical Induction, the proposition is true for integers n>=1.

To expand on ztibor's post about why it should be "natural numbers" not "reals": the process of induction relies on having a set, like the integers, where every element has a "next element" (such as 1 -> 2 -> 3 -> … for the naturals, or in the obvious way on the finite set {1,2,3}, for example). This works up to the rational numbers if you're cunning enough, but the reals can't be listed in this way (there is a neat proof of this; look up Cantor's Diagonal Argument if you're interested). Therefore induction won't work on the reals, because even if you keep going "for ever", you still won't hit all the numbers (although you will hit infinitely many of them). The reason is that we're working with two differently-sized infinities (the countable - things that can be put into a list - and the uncountable), and induction only works on the countable one (although transfinite induction, but that's a bit advanced :P )
It so happens that anything up to the rationals is countable (the rationals themselves are: I can assign each rational a natural number given by:

f(\frac{p}{q}) = 2^p 3^q 5^{sgn(p/q)+1}

where sgn gives -1 for a negative number, 0 for 0, and 1 for a positive. You can see that every rational number has its own unique natural number (by the uniqueness of factorisation) and given any number of the form 2^x 3^y 5^z, you can unambiguously construct the rational that gives that number. Hence the rationals can be counted out by the naturals, which is exactly what "countable" means. You can just put them in order of increasing f(p/q); clearly there are at least as many naturals as rationals, because eg. the number 7 is left over in the naturals according to this mapping, but there are also at least as many rationals as naturals because the rationals "contains" the naturals. Hence there are the same number of rationals as naturals.

Reply 5

amish123

OP

Original post by Indeterminate

When I did FP1 2 years back (time really does fly), I devised the following, which can be used regardless of whether you're proving the result over the reals, integers, etc.

"The result holds for n=k+1 as a consequence of the assumption that it holds for n=k. Hence, since it is true for n=1, it is true for all positive integers

n \geq 1

by induction "

1 is usually your base case, but you should obviously change the final line if it's different.

Thanks for your responses, I think I will use Inderterminate's statement as it is fairly short and easy to remember. I never actually fully understood what was going on during induction in terms of 'proof', however I can say that Smaug123 has really cleared things up, thanks :smile:

Reply 6

linnet18

Anyone got the Jan 2013 paper?

AQA FP2 - Proof by induction

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you