# Calculus II Proof by induction problem

1. Jan 17, 2013

### FinalStand

1. The problem statement, all variables and given/known data
Let a1=2, a2=0, a3=-14 and an+1=9an-23an-1+15an-2 for n>= 3. Show by induction that an=3n-1-5n-1+2 for n>=1.

2. Relevant equations

3. The attempt at a solution
Ok this is annoying to type...

Base Case is true, which is the easy part.

The induction part I am not going to list all the steps since it is a pain in the bum to write it out so here it is where I got stuck (it might be wrong too :P):

3n-5n+2 = an+1=9an-23an-1+15an-2

What do I do thanks?
1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution

2. Jan 17, 2013

### SammyS

Staff Emeritus
Well, I understand that the rules of this Forum require you to give somewhat more than you have given. Yes, I agree that typing this whole solution is pretty tedious .

What did you consider to be the Base Case?

What is it that you assume is true in showing that 3n-5n+2 = an+1 ?

3. Jan 17, 2013

### FinalStand

a1 = 3^(1-1) - 5^(1-1) + 2 = 2 since a1=2 base case is true

so for induction part n+1,

an+1 = 3^(n+1-1) - 5^(n+1-1) +2 which ends up as an+1 = 3^n - 5^n +2. I doubt you have to show these thouh. The rules I know, but this is enough information for this type of question....

4. Jan 17, 2013

### oli4

Hi FinalStand,
be careful with you base verification, it's not really what you are worried about right now I guess, but still be careful.
You didn't verify the base correctly, because this recurrence rule is not just 'if the previous is OK, than so is the next', there are 3 levels here, and you must be sure that your first 3 elements follow the rule.
If you don't, then you could use 'induction logic' to prove that, say, if the first two people you find in a room are women, than all people in the room are women for instance.
Anyway, first recheck your base and make it fully 'secured'
Then, just write the rule and verify that it works assuming everything behind it is verified, it isn't that complicated, but you have to write it clearly from the beginning.
So what do you want to show ?
$$a_{n+1}=9a_{n}-23a_{n-1}+15a_{n-2}=3^n-5^n+2$$
So once you base is secured, just replace the $$a_{n}, a_{n-1}, a_{n-2}$$ with their corresponding formula and after a couple of lines of putting everything together you should have your proof.

5. Jan 17, 2013

### FinalStand

I am now all confused again... what rule? dont you just sub in n=1 to the original equation? Sorry about this, I am still new to this proofing thing :P.

how do you replace the an, an-1 and etc..?

6. Jan 17, 2013

### FinalStand

I just proved one of them saying a1=2, so I have to prove that a2=0 and a3=-14? Well i just did that and they are all true. But how do you replace an, an-1, and an-2?

7. Jan 17, 2013

### oli4

Great, so now you have a good basis, (I didn't check it myself because I have little doubt, but it is important that you understand why this is important)
You have a formula that holds for an, you can look at it as a function of n, look at like this an=f(n) so you replace n by 'n-1' and 'n-2', you plug everything together and the proof should emerge.

8. Jan 17, 2013

### FinalStand

an=3^(n-1)-5^(n-1)+2 ......a(n-1) =3^(n-1-1) -5^(n-1-1)+2???

I need to confirm this...thanks

9. Jan 17, 2013

### oli4

Yes this is correct
I'm going to post it a bit more clearly later, but it will take some more time because I am not very familiar with tex :)

10. Jan 17, 2013

### SammyS

Staff Emeritus
The reason you need to include n=1, n=2 and n=3 in your Base Case is that you will be using the recurrence relation, an+1=9an-23an-1+15an-2 to prove the inductive step. If you only use n=1 for the Base Case, then the inductive step is proving the single term formula, an=3n-1-5n-1+2, for n ≥ 2. So for n=2, this would imply that you know a0 and a-1. However, a0 and a-1 are not defined.

You didn't fully answer my question regarding the assumptions needed to solve the inductive step:
What is it that you assume is true in showing that 3n-5n+2 = an+1 ? ​
What you assume is that an=3n-1-5n-1+2 is true for n≥1 ,

and

an+1=9an-23an-1+15an-2 is true for n≥3 .​

11. Jan 17, 2013

### oli4

So if you follow the rules, and now that you have seen that the first 3 elements follow the rule on which you base your induction, what you want to show is this
$$a_{n+1}=9a_n-23a_{n-1}+15a_{n-2}$$
with
$$a_n=3^{n-1}-5^{n-1}+2 => a_{n+1}=3^n-5^n+2$$
So
$$9a_n-23a_{n-1}+15a_{n-2}=3^n-5^n+2$$
So you want to show that
$$9(3^{n-1}-5^{n-1}+2)-23(3^{n-2}-5^{n-2}+2)+15(3^{n-3}-5^{n-3}+2)=3^n-5^n+2$$

12. Jan 17, 2013

### FinalStand

oli4 thanks. Sammy I still confused...do you have to show both base cases for the two equations given? where did you get n>=2 from ???

13. Jan 17, 2013

### oli4

FinalStand, you must understand what the proof by induction is all about and maybe step back from this particular problem.
the proof by induction says "I know that *this* is true and I have an induction rule that says, as long as *this* is true, then I can prove that it is true for all the other cases that follow".
In most cases, you will be asked to solve things like
a(n+1)=f(n), so in this case the *this* only depends on one previous element to be true and all the rest is true as well.
But in your current exercise, you have a(n+1)=f(n, n-1, n-2)
So for the reasoning to hold, you must make sure that wherever you start, (n=3, n=5, whatever), you have 3 cases right before you that hold true for the rule to assume them as a basis on which to build your proof.
Make sure you get that clear, solving your exercise by 'going ahead' where I left you is much less important than to clear your current confusion.

14. Jan 17, 2013

### SammyS

Staff Emeritus
I had something with n≥3 and something else with n≥1 .

You are given that $\ \ a_{n+1}=9a_n-23a_{n-1}+15a_{n-2}\ .\$ This relation only makes sense for n≥3, right? That's the reason you need n=1, n=2, and n=3 in your Base Case.