You are Here: Home >< Maths

# Proof by induction watch

Announcements
1. 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 for all natural numbers n, and , then .

Basis case: n=1.

True for P(1).

Inductive step:

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?

Edit - mistyped question.
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 for all natural numbers n, and , then .

Basis case: n=1.

True for P(1).

Inductive step:

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?

It should drop out simply from there.

Desired result to prove the statement by induction:

(notice that this is the same as you r inductive step, only you replace k by k+1!)
3. Given that you know what is, how do you find out what is?

Edit: I think you've missed a 3 out of the question somewhere...
4. 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.
5. 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)?
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 to so it would be a wise move

You don't show P(k). You assume it. Then show P(k+1).
7. 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 ).
8. New question:

Prove that if for natural numbers n. u1=1 u2=3, then

Got to the inductive step again:

P(k):

P(k+1):

.

Don't know how to go from here, too many terms. Can I just use and substitute them in? It seems presumptuous and circular though?
9. 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.
10. 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?
11. 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...
12. 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 and .
Use that fact that to show that
13. 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

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...
15. New Question:
"Prove by mathematical induction ".

Base case:

P(1):
LHS:
RHS: .

Inductive step:

P(k):

P(k+1):

Assuming P(k) is true:

Which would be great if it factorised to but I'm one out.

P.S. Why aren't my \sum 's working?
New Question:
"Prove by mathematical induction ".

Base case:

P(1):
LHS:
RHS: .

Inductive step:

P(k):

P(k+1):

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".

Assuming P(k) is true:

Which would be great if it factorised to but I'm one out.

See where I'm going?

P.S. Why aren't my \sum 's working?
Put \displaystyle at the start. (Quote me to see how.)
17. (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.

See where I'm going?
Aww, got it, not as "nice" as I would have hoped though.

Put \displaystyle at the start. (Quote me to see how.)
Thanks again.
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 (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".

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: August 22, 2007
Today on TSR

And I hate it

### University open days

• Heriot-Watt University
School of Textiles and Design Undergraduate
Fri, 16 Nov '18
• University of Roehampton
Sat, 17 Nov '18
• Edge Hill University
Faculty of Health and Social Care Undergraduate
Sat, 17 Nov '18
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