Proof by induction

[Queen_of_Random]

Hi, I got quite lost with those ones:

 

[Dr.Peterson]

Hi, I got quite lost with those ones:
View attachment 34313

We can't help you get unlost without some idea of where you are.

Please show your work and ask specific questions, as explained here:

Posting Guidelines (Summary)

Welcome to our tutoring boards! :) This page summarizes main points from our posting guidelines. As our name implies, we provide math help (primarily to students with homework). We do not generally post immediate answers or step-by-step solutions. We don't do your homework. We prefer to help...

www.freemathhelp.com

There are many different things you might be doing wrong, and we want to help with what you need, not with something else.

 

[Steven G]

The first one does not seem valid for a couple of reasons.

 

[Dr.Peterson]

The first one does not seem valid for a couple of reasons.

Yes, it should be

​

Both the formula for the term, and the formula for the sum, don't match the terms shown; but this fixes both.

And the second is unclear; the nth "term" is really the difference of two fractions:

​

It's definitely unusual.

 

[JeffM]

What is the base case for the third problem?

By the way, we ask in our guidelines that you not list multiple problems in a single thread and that you either show your work (even if you suspect it is wrong) or at least tell us with some specificity what your difficulty is.

 

[Steven G]

What is the base case for the third problem?

n=1, as a1 and a2 are given.

 

[Queen_of_Random]

Thank you for help and sorry for not following the guidlines - I must have overlooked them.
Now in the first and 3rd problem, I have a trouble with provng LHS=RHS:





In the 2nd one, I'm not sure what RHS should look like since it's also supposed to be a sum?

 

[Steven G]

2*3^2 = 6^2 is not correct! 2*3^2=2*9=18
So 5*2^(n+1) = 10^(n+1) is wrong!

 

[JeffM]

I am addressing only your third problem, which is a bit tricky.

$$\text {Given } a_1 = 5, \ a_2 = 13, \text { and } a_{n+2} = 5a_{n+1} - 6a_n \text { for any positive integer } n, \text {Prove } a_n = 2^n + 3^n.$$
What is tricky is figuring out how to start the induction. $a_1 = 5 = 2^1 + 3^1$ is necessary but trivial and does not help you with induction because $a_{-1}$ and $a_0$ are not defined.

Similarly, $a_2 = 13 = 4 + 9 = 2^2 + 3^2$ is necessary but trivial and does not help you with induction because $a_0$ is not defined.

So, we must start with $a_3$ as our base case for induction. It is not difficult if we see

$$n = 3 \implies a_3 = a_{1 + 2} = 5a_{1+1} - 6a_{1} \implies \\ a_{1+2} = 5a_2 - 6a_1 = 65 - 30 = 35 = 8 + 27 = 2^3 + 3^3 \implies\\ a_{1+2} = 2^{(1+2)} + 3^{(1+2)}.$$
Now we can say

$$a_1 = 2^1 + 3^1, \ a_2 = 2^2 + 3^2 =a_{1+1}, \text { and } a_3 = 2^3 + 4^3 = a_{1+2}.\\ \text {Let } k \text { be an ARBITRARY positive integer such that }\\ a_k = 2^k + 3^k, \ a_{k+1} = 2^{(k+1)} + 3^{(k+1)}, \text { and } a_{k+2} = 2^{(k+2)} + 3^{(k+2)}.$$
Now what?

 

[blamocur]

I am addressing only your third problem, which is a bit tricky.

$$\text {Given } a_1 = 5, \ a_2 = 13, \text { and } a_{n+2} = 5a_{n+1} - 6a_n \text { for any positive integer } n, \text {Prove } a_n = 2^n + 3^n.$$
What is tricky is figuring out how to start the induction. $a_1 = 5 = 2^1 + 3^1$ is necessary but trivial and does not help you with induction because $a_{-1}$ and $a_0$ are not defined.

Similarly, $a_2 = 13 = 4 + 9 = 2^2 + 3^2$ is necessary but trivial and does not help you with induction because $a_0$ is not defined.

So, we must start with $a_3$ as our base case for induction. It is not difficult if we see

$$n = 3 \implies a_3 = a_{1 + 2} = 5a_{1+1} - 6a_{1} \implies \\ a_{1+2} = 5a_2 - 6a_1 = 65 - 30 = 35 = 8 + 27 = 2^3 + 3^3 \implies\\ a_{1+2} = 2^{(1+2)} + 3^{(1+2)}.$$
Now we can say

$$a_1 = 2^1 + 3^1, \ a_2 = 2^2 + 3^2 =a_{1+1}, \text { and } a_3 = 2^3 + 4^3 = a_{1+2}.\\ \text {Let } k \text { be an ARBITRARY positive integer such that }\\ a_k = 2^k + 3^k, \ a_{k+1} = 2^{(k+1)} + 3^{(k+1)}, \text { and } a_{k+2} = 2^{(k+2)} + 3^{(k+2)}.$$
Now what?

Why can you start with $a_3$ but not with $a_0$? After all, $a_0 = \frac{5a_1-a_2}{6}$.

 

[JeffM]

Why can you start with $a_3$ but not with $a_0$? After all, $a_0 = \frac{5a_1-a_2}{6}$.

Whether there are restrictions on n is not explicitly specified.

Let‘s follow your hypothesis through and assume that n can be any integer.

$$a_{0+2} = 5a_{0+1} - 6a_0 \implies a_2 = 5a_1 - 6a_0 \implies \\ a_0 = \dfrac{5a_1 - a_2}{6} = \dfrac{5 * 5 - 13}{6} = \dfrac{12}{6} = 2 = 1 + 1 = 2^0 + 3^0.\\ a_{-1+2} = 5a_{-1+1} - 6a_{-1} \implies a_1 = 5a_0 - 6a^{-1} \implies \\ a_{-1} = \dfrac{5a_0 - a_1}{6} = \dfrac{5 * 2 - 5}{6} = \dfrac{5}{6} = \dfrac{3}{6} + \dfrac{2}{6} = \dfrac{1}{2} + \dfrac{1}{3} = 2^{-1} + 3^{-1}.$$
I simply assumed that n was restricted to positive integers. Silly me.

 

[blamocur]

I simply assumed that n was restricted to positive integers. Silly me.

I am a retired software engineer, so 0 seems like a natural first index to me And it's been a while since I've written anything in Fortran

 

[Deleted member 4993]

I am a retired software engineer, so 0 seems like a natural first index to me And it's been a while since I've written anything in Fortran

I think JeffM is a retired banker → he does not like 0 as a starting number !!

 

[Dr.Peterson]

I expect an induction proof to start with the given values (n=1, 2) and go up from there. Induction proofs for all integers are less often assigned. So my guess would be that they mean positive integers, based on that.

But the problem should have stated the domain.

 

[Steven G]

Whether there are restrictions on n is not explicitly specified.

Let‘s follow your hypothesis through and assume that n can be any integer.

$$a_{0+2} = 5a_{0+1} - 6a_0 \implies a_2 = 5a_1 - 6a_0 \implies \\ a_0 = \dfrac{5a_1 - a_2}{6} = \dfrac{5 * 5 - 13}{6} = \dfrac{12}{6} = 2 = 1 + 1 = 2^0 + 3^0.\\ a_{-1+2} = 5a_{-1+1} - 6a_{-1} \implies a_1 = 5a_0 - 6a^{-1} \implies \\ a_{-1} = \dfrac{5a_0 - a_1}{6} = \dfrac{5 * 2 - 5}{6} = \dfrac{5}{6} = \dfrac{3}{6} + \dfrac{2}{6} = \dfrac{1}{2} + \dfrac{1}{3} = 2^{-1} + 3^{-1}.$$
I simply assumed that n was restricted to positive integers. Silly me.

Jeff, I replied to your question earlier saying you start with n=1. Since the formula was a_(n+2)= 5a_(n+1) - 6a_n, you start with n=1, as that tell you what a_3 equals--which is the starting point.

 

[JeffM]

Jeff, I replied to your question earlier saying you start with n=1. Since the formula was a_(n+2)= 5a_(n+1) - 6a_n, you start with n=1, as that tell you what a_3 equals--which is the starting point.

No, I understood your point. I just was not sure the OP was with us.