Turn on thread page Beta
    • Thread Starter
    Offline

    2
    ReputationRep:
    Hi,

    I'm learning this from a book, and it doesn't go through any examples with recurrence relations, but here is my attempt:

    "Prove that if u_{n+1}=3u_n+4 for all natural numbers n, and u_1=2, then u_n=4\times3^{n-1}-2.

    Basis case: n=1.

    u_1=(4\times3^0)-2=2

    True for P(1).

    Inductive step:

    u_k=(4\times3^{k-1})-2

    I am unsure how to proceed, I don't really have a clear goal, what am I trying to do? I don't know which equation I substitute k+1 into?

    Just advice, no work throughs please guys, thanks.

    Edit - mistyped question.
    Offline

    2
    ReputationRep:
    (Original post by Adthegreat)
    Hi,

    I'm learning this from a book, and it doesn't go through any examples with recurrence relations, but here is my attempt:

    "Prove that if u_{n+1}=u_n+4 for all natural numbers n, and u_1=2, then u_n=4\times3^{n-1}-2.

    Basis case: n=1.

    u_1=(4\times3^0)-2=2

    True for P(1).

    Inductive step:

    u_k=(4\times3^{k-1})-2

    I am unsure how to proceed, I don't really have a clear goal, what am I trying to do? I don't know which equation I substitute k+1 into?

    Just advice, no work throughs please guys, thanks.
    Shove the inductive step into u_{n+1}=u_n+4. i.e. start with:

    u_{k+1}=u_k+4 = [(4\times3^{k-1})-2] + 4

    It should drop out simply from there.

    Desired result to prove the statement by induction:

    u_{k+1} = (4\times3^{k})-2
    (notice that this is the same as you r inductive step, only you replace k by k+1!)
    Offline

    13
    ReputationRep:
    Given that you know what u_k is, how do you find out what u_{k+1} is?

    Edit: I think you've missed a 3 out of the question somewhere...
    Offline

    15
    ReputationRep:
    firstly, you appear to be trying to prove the converse of what is asked. secondly, u_n+1 - u_n clearly is not 4 if u_n is 4.3^(n-1) - 2. it's 8.3^(n-1).

    all in all, i'm confused.
    • Thread Starter
    Offline

    2
    ReputationRep:
    Absolutely right, I mistyped the question.

    So anyway, do i use the equation that involves both u_k and u_{k+1} where possible, after showing P(k)?
    Offline

    13
    ReputationRep:
    (Original post by Adthegreat)
    Absolutely right, I mistyped the question.

    So anyway, do i use the equation that involves both u_k and u_{k+1} where possible, after showing P(k)?
    Well it's the only thing you've got to connect u_k to u_{k+1} so it would be a wise move

    You don't show P(k). You assume it. Then show P(k+1).
    • Thread Starter
    Offline

    2
    ReputationRep:
    Ok so I throw it in there, then say that it is equivalent to the second equation where n=k+1. If so, I've got it (evidently :p:).
    • Thread Starter
    Offline

    2
    ReputationRep:
    New question:

    Prove that if u_{n+2}=3u_{n+1}-2u_{n} for natural numbers n. u1=1 u2=3, then u_{n}=2^n-1

    Got to the inductive step again:

    P(k):

    u_{k+2}=3u_{k+1}-2u_k

    P(k+1):

    u_{k+3}=3u_{k+2}-2u_{k+1}.

    Don't know how to go from here, too many terms. Can I just use u_n=2^n-1 and substitute them in? It seems presumptuous and circular though?
    • Wiki Support Team
    Offline

    14
    ReputationRep:
    Wiki Support Team
    It is circular.

    You obviously want to get rid of the u_k term, so start by doing that. After that, personally, I'd add a u_(k+3) to both sides and fiddle around with one of them to get it in terms of u_(k+2) and u_(k+1), and that should hopefully be the answer.

    Edit: hold on, what? That's not what you should be doing at all.

    You're given u_(n+2) = blah. You want to prove that u_n = 2^n - 1, so assume that u_(k-1) = 2^(k-1) - 1 and u_k = 2^k - 1 and then prove from there that u_(k+1) = 2^(k+1) - 1.
    • Thread Starter
    Offline

    2
    ReputationRep:
    So have I done most of the process wrong. I needed to show P(k) in u_n=2^n -1? And I don't understand where the k-1 has come from?
    • Wiki Support Team
    Offline

    14
    ReputationRep:
    Wiki Support Team
    For a start,
    P(n): u_n = 2^n - 1.

    That's your proposition. That's what you're trying to prove. Now, obviously, you need to assume P(k) somewhere along the line because this is induction. But that's not sufficient to imply P(k+1), in this case (try it and you'll see why). However, if we assume P(k-1) too, we can prove P(k+1).

    This is justified because we can show P(1) and P(2) (given in the question). If P(1) and P(2), then P(3). But if P(2) and P(3), then P(4), etc...
    Offline

    13
    ReputationRep:
    The strategy here is:
    Prove P(1) and P(2) for the base.

    Assume P(k-1) and P(k).
    Prove P(k+1).

    That is, assume that u_{k-1}=2^{k-1} - 1 and u_k = 2^k - 1.
    Use that fact that  u_{k+1} = 3u_k - 2u_{k-1} to show that u_{k+1} = 2^{k+1} - 1
    • Thread Starter
    Offline

    2
    ReputationRep:
    Ok got it. Also works out if you assume P(k) and P(k+1) and prove P(k+2). It's a shame my book doesn't mention this. Maybe because you lot did this in FP3 and in OCR it's in FP1

    Thanks for all your help.
    Offline

    13
    ReputationRep:
    (Original post by Adthegreat)
    Ok got it. Also works out if you assume P(k) and P(k+1) and prove P(k+2).
    Yes, exactly (provided you've proved P(1) and P(2)). This can happen to be very handy...
    • Thread Starter
    Offline

    2
    ReputationRep:
    New Question:
    "Prove by mathematical induction \sum_{r=1}^{n}2r>n^2".

    Base case:

    P(1):
    LHS: \sum_{r=1}^{1}2r=2
    RHS: 1^2=1.

    Inductive step:

    P(k):
    \sum_{r=1}^{k}2r=2+4+6+..+2k

    P(k+1):
    \sum_{r=1}^{k+1}2r=2+4+6+..+2k+2  (k+1)

    \sum_{r=1}^{k+1}2r= (\sum_{r=1}^{k}2r)+2k+2

    \sum_{r=1}^{k+1}2r= P(k)+2k+2

    Assuming P(k) is true:

    \sum_{r=1}^{k+1}2r>k^2+2k+2

    Which would be great if it factorised to (k+1)^2 but I'm one out.

    P.S. Why aren't my \sum 's working?:mad:
    • Wiki Support Team
    Offline

    14
    ReputationRep:
    Wiki Support Team
    (Original post by Adthegreat)
    New Question:
    "Prove by mathematical induction \sum_{r=1}^{n}2r>n^2".

    Base case:

    P(1):
    LHS: \sum_{r=1}^{1}2r=2
    RHS: 1^2=1.

    Inductive step:

    P(k):
    \sum_{r=1}^{k}2r=2+4+6+..+2k

    P(k+1):
    \sum_{r=1}^{k+1}2r=2+4+6+..+2k+2  (k+1)

    \sum_{r=1}^{k+1}2r= (\sum_{r=1}^{k}2r)+2k+2

    \sum_{r=1}^{k+1}2r= P(k)+2k+2
    Ack. P(k) isn't an expression in k, it's a statement! You can't use it like this; "P(k)" means "2 + 4 + ... + 2k > k^2".

    (Original post by Adthegreat)
    Assuming P(k) is true:

    \sum_{r=1}^{k+1}2r>k^2+2k+2

    Which would be great if it factorised to (k+1)^2 but I'm one out.
    \displaystyle \sum_{r=1}^{k+1}2r>k^2+2k+2 > k^2 + 2k + 1
    See where I'm going?

    (Original post by Adthegreat)
    P.S. Why aren't my \sum 's working?:mad:
    Put \displaystyle at the start. (Quote me to see how.)
    • Thread Starter
    Offline

    2
    ReputationRep:
    (Original post by generalebriety)
    Ack. P(k) isn't an expression in k, it's a statement! You can't use it like this; "P(k)" means "2 + 4 + ... + 2k > k^2".
    Right, thanks, I never know how to set these out properly.

    \displaystyle \sum_{r=1}^{k+1}2r>k^2+2k+2 > k^2 + 2k + 1
    See where I'm going?
    Aww, got it, not as "nice" as I would have hoped though. :p:

    Put \displaystyle at the start. (Quote me to see how.)
    Thanks again.
    • Wiki Support Team
    Offline

    14
    ReputationRep:
    Wiki Support Team
    (Original post by Adthegreat)
    Right, thanks, I never know how to set these out properly.
    I see. P is a proposition; essentially, you define P(n) as the statement \displaystyle '' \sum_{r=1}^n 2n > n^2 '' (left hand side is greater than right hand side), so "P(k)" means "that statement holds true for k", and similarly "P(k+1)" means "that statement holds true for k+1".
 
 
 
Reply
Submit reply
Turn on thread page Beta
Updated: August 22, 2007

University open days

  • Heriot-Watt University
    School of Textiles and Design Undergraduate
    Fri, 16 Nov '18
  • University of Roehampton
    All departments Undergraduate
    Sat, 17 Nov '18
  • Edge Hill University
    Faculty of Health and Social Care Undergraduate
    Sat, 17 Nov '18
Poll
Have you ever experienced bullying?
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

Equations

Best calculators for A level Maths

Tips on which model to get

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

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

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