You are Here: Home >< Maths

AQA FP2 - Proof by induction Watch

1. 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!
2. 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
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!
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.
4. (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 by induction "

1 is usually your base case, but you should obviously change the final line if it's different.
5. 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: 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.
6. (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 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
7. Anyone got the Jan 2013 paper?

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: May 18, 2013
Today on TSR

Last-minute PS help

100s of personal statements examples here

More pressure for kinky sex?

Discussions on TSR

• Latest
• See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• Poll
Useful resources

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

How to use LaTex

Writing equations the easy way

Study habits of A* students

Top tips from students who have already aced their exams

Chat with other maths applicants

Groups associated with this forum:

View associated groups
Discussions on TSR

• Latest
• See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.