Proof by induction help

Maths and statistics discussion, revision, exam and homework help.

This thread is sponsored by:
Announcements Posted on
Important: please read these guidelines before posting about exams on The Student Room 28-04-2013
Search Thread
Advanced Search
Sign in to Reply
  1. thorn0123's Avatar
    1 15-06-2012  01:15
    • Adored and Respected Member
    • Posts: 462
    Proof by induction help


    Could anyone explain to me for part a) what they have done here (the highlight parts)



    For part b) Would my working here get full marks?

    f(n) = 3^{n+2} + (-1)^n2^n
    n = 1
    f(1) = 3^3 + (-1)(2) = 25
    so true for n = 1
    assume true for n = k
    \mathrm{i.e\ } 3^{k+2} +(-1)^k(2)^k

    n = k+1

    f(k+1) = 3^{k+3} + 2^{k+1}(-1)^{k+1}
    f(k+1) = 3^3(3^k) + 2(2)^k(-1)(-1)^k
    f(k+1) = 27(3^k) + 2(2)^k(-1)(-1)^k
    2f(k+1) = 54(3^k) -4(2)^k(-1)^k
    2f(k+1) - f(k) = 54(3^k) -4(2)^k(-1)^k -3^{k+2}-2^k(-1)^k
    2f(k+1) - f(k) = 54(3^k) -4(2)^k(-1)^k -9(3)^k -(2)^k(-1)^k
    2f(k+1) = f(k) + 45(3)^k -5(2)^k(-1)^k

    As f(k) \mathrm{and\ } 45(3)^k -5(2)^k(-1)^k are true then the sum of them is also true, therefore f(k+1) is divisible by 5.

    As true for n = 1 => true for n>= 1 neZ+
    True for n=k then as shown true for n=k+1 by mathematical induction

    Is this sufficient as they have done different working.

    thanks
  2. notnek's Avatar
    2 15-06-2012  04:27
    • TSR Demigod
    • Location: Bangkok, Thailand
    Re: Proof by induction help
    b)

    You have shown that 2f(k+1) is div by 5 but you should write a bit why this implies that f(k+1) is div by 5.

    Also, your statement "f(k)... are true" doesn't make much sense since f(k) is an expression not an equation. Try to keep your induction proofs mathematically as well as grammaticaly valid.
  3. notnek's Avatar
    3 15-06-2012  04:36
    • TSR Demigod
    • Location: Bangkok, Thailand
    Re: Proof by induction help
    a)

    \displaystyle \sum _{r=1}^{k+1} f(r) =\sum _{r=1}^{k} f(r) + \sum _{r=k+1}^{k+1} f(r) = \left(\sum_{r=1}^k f(r)\right) + f(k+1)

    Does this make sense to you and does it help with the first part?


    Second part:


    \displaystyle -\left(\frac{1}{2}\right)^{k-1}+ \left(\frac{1}{2}\right)^{k} = - \left(\frac{1}{2}\right)^{k-1}+ \frac{1}{2}\times \left(\frac{1}{2}\right)^{k-1}

    \displaystyle = \left(\frac{1}{2}\right)^{k-1}\left(-1+\frac{1}{2}\right)
    Last edited by notnek; 15-06-2012 at 05:15.
  4. thorn0123's Avatar
    4 15-06-2012  07:22
    • Adored and Respected Member
    • Posts: 462
    Re: Proof by induction help
    (Original post by notnek)
    a)

    \displaystyle \sum _{r=1}^{k+1} f(r) =\sum _{r=1}^{k} f(r) + \sum _{r=k+1}^{k+1} f(r) = \left(\sum_{r=1}^k f(r)\right) + f(k+1)

    Does this make sense to you and does it help with the first part?


    Second part:


    \displaystyle -\left(\frac{1}{2}\right)^{k-1}+ \left(\frac{1}{2}\right)^{k} = - \left(\frac{1}{2}\right)^{k-1}+ \frac{1}{2}\times \left(\frac{1}{2}\right)^{k-1}

    \displaystyle = \left(\frac{1}{2}\right)^{k-1}\left(-1+\frac{1}{2}\right)
    I'm still lost on part a), I don't see the first part how it would be (k+1), I thought it would be (k+1)/2 *(k+1+2) + (1/2)^k .

    Also, how do they get (-1+1/2)?
  5. notnek's Avatar
    5 15-06-2012  07:33
    • TSR Demigod
    • Location: Bangkok, Thailand
    Re: Proof by induction help
    (Original post by thorn0123)
    I'm still lost on part a), I don't see the first part how it would be (k+1), I thought it would be (k+1)/2 *(k+1+2) + (1/2)^k .
    Could you explain which specific (k+1) you are talking about and could you also say why you think it should be (k+1)/2 *(k+1+2) + (1/2)^k ?

    I can help you if I understand your reasoning.

    Also, how do they get (-1+1/2)?
    They have factorised. The first term is (-1) times (\frac{1}{2})^{k-1} and the second term is (1/2) times (\frac{1}{2})^{k-1} so you can take out a factor of (\frac{1}{2})^{k-1}.

    Again, if you're still confused, can you tell me the specific part which you're confused about?
  6. thorn0123's Avatar
    6 15-06-2012  19:10
    • Adored and Respected Member
    • Posts: 462
    Re: Proof by induction help
    (Original post by notnek)
    Could you explain which specific (k+1) you are talking about and could you also say why you think it should be (k+1)/2 *(k+1+2) + (1/2)^k ?

    I can help you if I understand your reasoning.


    They have factorised. The first term is (-1) times (\frac{1}{2})^{k-1} and the second term is (1/2) times (\frac{1}{2})^{k-1} so you can take out a factor of (\frac{1}{2})^{k-1}.

    Again, if you're still confused, can you tell me the specific part which you're confused about?
    Well for part a) I thought the series would be for n = k+1 :

    \displaystyle\sum_{r=1}^{k+1}r + (\frac{1}{2})^{k+1-1}
    2 + \frac{7}{2} + \frac{25}{4} +... \frac{k}{2}(k+1) + (\frac{1}{2})^{k-1} + \frac{k+1}{2}(k+2) + (\frac{1}{2})^k
    \frac{1}{2}(k^2+k+4)-(\frac{1}{2})^{k-1} + (\frac{k+1}{2}(k+2) + (\frac{1}{2})^k)

    and in the solution they are saying add (k+1) + (1/2)^k to each side, but I don't understand why.

    I am also doing (k+1)/2 (k+2) because the \displaystyle\sum_{r=1}^{n}r is \frac{n}{2}(n+1)

    Thank you again for helping
  7. notnek's Avatar
    7 15-06-2012  20:54
    • TSR Demigod
    • Location: Bangkok, Thailand
    Re: Proof by induction help
    (Original post by thorn0123)
    Well for part a) I thought the series would be for n = k+1 :

    \displaystyle\sum_{r=1}^{k+1}r + (\frac{1}{2})^{k+1-1}
    2 + \frac{7}{2} + \frac{25}{4} +... \frac{k}{2}(k+1) + (\frac{1}{2})^{k-1} + \frac{k+1}{2}(k+2) + (\frac{1}{2})^k
    \frac{1}{2}(k^2+k+4)-(\frac{1}{2})^{k-1} + (\frac{k+1}{2}(k+2) + (\frac{1}{2})^k)

    and in the solution they are saying add (k+1) + (1/2)^k to each side, but I don't understand why.

    I am also doing (k+1)/2 (k+2) because the \displaystyle\sum_{r=1}^{n}r is \frac{n}{2}(n+1)

    Thank you again for helping
    What you are doing is not necessary and makes the question more complicated. I'll try to explain again what the solution has done because this technique is used in most induction questions involving summations.

    Here's a simpler example that might help you:

    \displaystyle \sum_{r=1}^k 2^r = 2+4+8+...+2^{k-1}+2^{k}

    \displaystyle \sum_{r=1}^{k+1} 2^r = 2+4+8+...+2^{k-1}+2^{k} + 2^{k+1}

    The 1st line -> 2nd line is equivalent to adding 2^{k+1} i.e. f(k+1) in my second post, to both sides. Can you see how a very similar thing has been done in your example?


    Your textbook should be able to explain this better than I can.
    Last edited by notnek; 15-06-2012 at 20:55.
Sign in to Reply
Search Thread
Advanced Search
Share this discussion:  
Useful resources

Articles:

Study Help rules and posting guidelinesStudy Help Member of the Month nominationsGuide to MathematicsMathematics resourcesMathematics websitesMathematics revision notes in the TSR wikiCambridge Assessment admissions tests (including STEP)How to use LaTeXCareers in Mathematics

Useful Dates:

Quick Link:

Unanswered Maths Threads

Groups associated with this forum:

View associated groups
Article updates
Moderators

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

This forum is moderated by:

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

Shortcuts

Get Started

TSR Group

Using TSR

Info

Connect with TSR

Reputation gems:
The Reputation gems seen here indicate how well reputed the user is, red gem indicate negative reputation and green indicates a good rep.
Post rating score:
These scores show if a post has been positively or negatively rated by our members.