Calculus II Proof by induction problem

[FinalStand]

Homework Statement

Let a₁=2, a₂=0, a₃=-14 and a_n+1=9a_n-23a_n-1+15a_n-2 for n>= 3. Show by induction that a_n=3^n-1-5^n-1+2 for n>=1.

Homework Equations

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):

3ⁿ-5ⁿ+2 = a_n+1=9a_n-23a_n-1+15a_n-2

What do I do thanks?

Homework Statement

Homework Equations

The Attempt at a Solution

 

[SammyS]

Homework Statement

Let a₁=2, a₂=0, a₃=-14 and a_n+1=9a_n-23a_n-1+15a_n-2 for n>= 3. Show by induction that a_n=3^n-1-5^n-1+2 for n>=1.

Homework Equations

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):

3ⁿ-5ⁿ+2 = a_n+1=9a_n-23a_n-1+15a_n-2

What do I do thanks?

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 3ⁿ-5ⁿ+2 = a_n+1 ?

 

[FinalStand]

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

so for induction part n+1,

a_n+1 = 3^(n+1-1) - 5^(n+1-1) +2 which ends up as a_n+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...

 

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

 

[FinalStand]

I am now all confused again... what rule? don't 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..?

 

[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?

 

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

 

[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

 

[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 :)

 

[SammyS]

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?

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, a_n+1=9a_n-23a_n-1+15a_n-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, a_n=3^n-1-5^n-1+2, for n ≥ 2. So for n=2, this would imply that you know a₀ and a_-1. However, a₀ 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 3ⁿ-5ⁿ⁺² = a_n+1 ?​

To answer that ...

What you assume is that a_n=3^n-1-5^n-1+2 is true for n≥1 ,

and

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

 

[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$$
So... go ahead :)

 

[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 ?

 

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

 

[SammyS]

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 ?

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.