Hey there! Sign in to join this conversationNew here? Join for free
    • Thread Starter
    Offline

    0
    ReputationRep:
    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!
    Offline

    0
    ReputationRep:
    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
    Offline

    3
    ReputationRep:
    (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.
    • Political Ambassador
    Offline

    3
    ReputationRep:
    Political Ambassador
    (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.
    • PS Helper
    • Study Helper
    Offline

    13
    ReputationRep:
    PS Helper
    Study Helper
    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.
    • Thread Starter
    Offline

    0
    ReputationRep:
    (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
    Offline

    0
    ReputationRep:
    Anyone got the Jan 2013 paper?
 
 
 
  • 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
    Brussels sprouts
    Useful resources

    Make your revision easier

    Maths

    Maths Forum posting guidelines

    Not sure where to post? Read the updated guidelines here

    Equations

    How to use LaTex

    Writing equations the easy way

    Student revising

    Study habits of A* students

    Top tips from students who have already aced their exams

    Study Planner

    Create your own Study Planner

    Never miss a deadline again

    Polling station sign

    Thinking about a maths degree?

    Chat with other maths applicants

    Can you help? Study help unanswered threads

    Groups associated with this forum:

    View associated groups
  • 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

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