Calculus II Proof by induction problem

  • Thread starter FinalStand
  • Start date
  • #1
60
0

Homework Statement


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.


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

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

What do I do thanks?

Homework Statement





Homework Equations





The Attempt at a Solution

 

Answers and Replies

  • #2
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,317
1,007

Homework Statement


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.

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

3n-5n+2 = an+1=9an-23an-1+15an-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 3n-5n+2 = an+1 ?
 
  • #3
60
0
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
218
1
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 ?
[tex]a_{n+1}=9a_{n}-23a_{n-1}+15a_{n-2}=3^n-5^n+2[/tex]
So once you base is secured, just replace the [tex]a_{n}, a_{n-1}, a_{n-2}[/tex] with their corresponding formula and after a couple of lines of putting everything together you should have your proof.
 
  • #5
60
0
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
60
0
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
218
1
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
60
0
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
218
1
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
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,317
1,007
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, 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 ?​
To answer that ...
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
218
1
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
[tex]a_{n+1}=9a_n-23a_{n-1}+15a_{n-2}[/tex]
with
[tex]a_n=3^{n-1}-5^{n-1}+2 => a_{n+1}=3^n-5^n+2[/tex]
So
[tex]9a_n-23a_{n-1}+15a_{n-2}=3^n-5^n+2[/tex]
So you want to show that
[tex]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[/tex]
So... go ahead :)
 
  • #12
60
0
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
218
1
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
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,317
1,007
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 [itex]\ \ a_{n+1}=9a_n-23a_{n-1}+15a_{n-2}\ .\ [/itex] 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.
 

Related Threads on Calculus II Proof by induction problem

  • Last Post
Replies
1
Views
955
  • Last Post
Replies
11
Views
1K
  • Last Post
Replies
2
Views
757
Replies
2
Views
1K
  • Last Post
Replies
6
Views
786
Replies
3
Views
1K
Replies
8
Views
857
  • Last Post
Replies
1
Views
469
Replies
5
Views
1K
  • Last Post
Replies
8
Views
2K
Top