Proof by induction help!

Hi,

I'm kinda stuck on proof by induction.
I get the simple ones and the actual inductive step for 'more complex' ones, but I don't get the basis part of the complex ones.

So for example u_n+2=5u_n+1-6u_n, u₁=13, and u_n=2ⁿ⁺¹ +3ⁿ⁺¹.

It proves u_n works for n=1, 2 and 3, but I don't see why we need all three.
If we know it works for n=1, surely we would know it works for 2 and so on?

Also, it also assumes u_n=2ⁿ⁺¹ +3ⁿ⁺¹ correct for n=k and n=k+1.
Why does it do that?
If it works for n=k wouldn't it work for n=k+1 anyway?

Thanks!

The way induction normally works is that we show it is true for the base case (normally n=1). Then, we assume it is true for some arbitrary value n=k and show that if it is true for n=k then it is true for n=k+1.
Since we know it is true for n=1, we know it is true for n=2 (if true for n=k, then true for n=k+1) and 3 and 4 and so on..

Here we need a slightly different argument.

We still need to show the basis case.We need to show it is true for n=1,2,3 just to show that the sequence itself also works. (the sequence requires three successive terms, so we calculate u₁ , u₂ and u₃ , showing that they all satisfy the definition of u_n that we are trying to prove, and then showing that they satisfy that sequence that we are trying to figure out what u_n actually is)
Basically we have a sequence: u_n+2=5u_n+1-6u_n
and we are trying to prove that the general term is: u_n=2ⁿ⁺¹ +3ⁿ⁺¹

Here, we have done our base case, so we have to assume it is true for n=k AND n=k+1 as those are the two terms in our sequence. We now need to show if it is true for both n=k and n=k+1, and we shove it into the definition of our sequence (that is that u_n+2=5u_n+1-6u_n) then we will get a general term for u_k+2. We hope, and know we have been successful when, this term looks like the thing we are trying to prove.

We conclude by saying that if it is true for both n=k and n=k+1 , then it is true for n=k+2.
Since it is true for n=1 and 2 (and also 3 since we did this just to check the sequence worked) it is true for n=4,5.... in the same way as before.

I hoped this helped as I appreciate these are the harder induction questions (if you are doing FP1 Edexcel which is what i did last year:P)

If we assume n=k to be true, won't n=k+1 be true as well just by substitution?Also, when we are shoving these into the definition of the sequence, surely we have used the sequence, so we don't have to show only n=1 is true..?I think I'm missing something and confusing myself...:'(

The point of induction isn't to assume anything about n=k+1.
If you forget about the letters for a sec and think about the ideas it might make it a bit easier. We just assume it holds true for a general case. Then we try to show IF it is true for that case, and we do some algebra and stuff, then we work out what the next case will be, if this looks how we think it should do then what we have done is say okay well if its true for a general case, then it also happens to be true for the case after that aswell.

I know what you mean by saying well surely its true for the next case by substitution, but we arent saying anything is true in our argument, we are saying Suppose it is true for n=k and we work (using this assumption) and do some maths and show that if we assume its true for n=k, then it also happens to be true for n=k+1.

Does this thinking make sense or should I try and explain it differently, it is quite a weird concept to get used to at first

I do understand the logic of proof by induction, but I still can't find the answer for my initial two questions.. Why do we need to show that all n=1,2 and 3 are correct?
Thanks for helping

Please read the following slowly and carefully. This is tricky subject to explain and understand.


You don't actually need to show n = 3 but you do need n = 1 and n = 2.

You're used to doing a proof by induction by proving true for n = 1. Then you prove that 'if n=k is true then n=k+1 is true'. This produces a domino effect : since you have n = 1, the above proof shows that n = 2 is true, which shows that n = 3 is true etc. -> infinity.

Please tell us if you're not confident with the above.


It would be great if you could do the same thing for your question : if you can prove that 'if n=k is true then n=k+1 is true' and then show that n = 1 works then you're done.

But you can't do that here because all you have to work with is a recurrence relation involving $u_n, u_{n+1}$ and $u_{n+2}$.

So you need a different approach. The approach is to prove that 'if n=k and n=k+1 is true then n=k+2 is true'.

If you prove that then just doing the base step for n=1 wouldn't be enough. But if you show that n=1 and n=2 is true then this domino effect happens again:

n = 1, n = 2 -> n=3
n = 2, n = 3 -> n=4
etc.

And you're done. If you're still stuck please tell me the exact part of my post where you first got stuck.


I'm basically repeating what Rjix said (who I thought explained it very well). But it may help you to get a second explanation.

I am comfortable with the concept, and what was really bothering me was that the textbook showed n= 1,2 and 3 which suggested my thinking was wrong!

'You don't actually need to show n = 3 but you do need n = 1 and n = 2.' solved that problem - thank you.
But you still haven't answered my second question: why do we need to assume n=k as well as n=k+1? surely if n=k is true n=k+1 will be true just by substitution?

Thanks!

Your initial post make it look like you thought you only needed n=1. This is why I assumed your thinking was incorrect. You should have been clearer.

Can you explain what you mean by 'substitution'?

"if n=k is true n=k+1 will be true just by substitution"

If this is correct then the proof is done before you've even started.