# Calculus II Proof by induction problem

• FinalStand
In summary: So for n=2, this would imply that you know a0 and a-1. However, a0 and a-1 are not defined.In summary, the homework statement states that an equation holds for an, a function of n, if the base case is true. The induction part states that for n>=1, an=3n-1-5n-1+2.
FinalStand

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

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

FinalStand said:

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

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

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

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.

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

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?

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.

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

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

FinalStand said:
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 ?​
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 .​

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$$

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 ?

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.

FinalStand said:
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.

## What is the concept of proof by induction in Calculus II?

Proof by induction is a mathematical technique used to prove statements or theorems that involve an infinite number of elements. It is commonly used in Calculus II to prove theorems involving sequences, series, and limits.

## How does proof by induction work?

The basic idea behind proof by induction is to show that a statement is true for the first element, and then show that if it is true for any element, it must also be true for the next element. This process is repeated until the statement is shown to be true for all elements in the set.

## What are the steps involved in a proof by induction?

The steps involved in a proof by induction include:
1. Proving the statement is true for the first element
2. Assuming the statement is true for any arbitrary element
3. Using this assumption to prove that the statement is also true for the next element
4. Repeating this process until the statement is shown to be true for all elements
5. Concluding that the statement is true for all elements in the set.

## When is proof by induction used in Calculus II?

Proof by induction is commonly used in Calculus II to prove theorems involving sequences, series, and limits. It is also used in other branches of mathematics such as algebra and number theory.

## What are some common mistakes to avoid when using proof by induction?

Some common mistakes to avoid when using proof by induction include:
1. Assuming that the statement is true for all elements without proving it for the first element
2. Using circular reasoning by assuming the statement is true for the next element in order to prove that it is true for the current element
3. Skipping steps in the inductive process
4. Using incorrect assumptions or not clearly stating the assumptions
5. Forgetting to conclude the proof by showing that the statement is true for all elements in the set.

• Calculus and Beyond Homework Help
Replies
15
Views
2K
• Calculus and Beyond Homework Help
Replies
7
Views
624
• Calculus and Beyond Homework Help
Replies
4
Views
7K
• Calculus and Beyond Homework Help
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
3
Views
2K
• Calculus and Beyond Homework Help
Replies
4
Views
1K
• Calculus and Beyond Homework Help
Replies
5
Views
2K
• Calculus and Beyond Homework Help
Replies
29
Views
4K
• Calculus and Beyond Homework Help
Replies
6
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
1K