Thread: [SOLVED] Recursive sequence induction proof

Define $\displaystyle b_n$ as $\displaystyle b_0 = 0$ , $\displaystyle b_1 = 3$ and $\displaystyle b_n = 7b_{n-1}-10b_{n-2}$. Prove by induction that $\displaystyle b_n=5^n-2^n$

Proof:

Let P(n) be the propositional statement for n>1 "$\displaystyle 5^n-2^n=7b_{n-1}-10b_{n-2}$"

The LHS of P(2) is 5^2-2^2=21 and the RHS if P(2) is 7(3)-10(0)=21. So P(2) is true.

Now assume that P(j) is true for all j<k. That is assume $\displaystyle 5^j-2^j=7b_{j-1}-10b_{j-2}$. Then by this assumption that P(j-1) can be written as $\displaystyle 7(5^{k-1}-2^{k-1})-10(5^{k-2}-2^{k-2})$

Now I'm kind of stuck. This is either going to take some sick algebra or I made a boo-boo.

Originally Posted by Jameson

Define $\displaystyle b_n$ as $\displaystyle b_0 = 0$ , $\displaystyle b_1 = 3$ and $\displaystyle b_n = 7b_{n-1}-10b_{n-2}$. Prove by induction that $\displaystyle b_n=5^n-2^n$

Proof:

Let P(x) be the propositional statement for n>1 "$\displaystyle 5^n-2^n=7b_{n-1}-10b_{n-2}$"

The LHS of P(2) is 5^2-2^2=21 and the RHS if P(2) is 7(3)-10(0)=21. So P(2) is true.

Now assume that P(j) is true for all j<k. That is assume $\displaystyle 5^j-2^j=7b_{j-1}-10b_{j-2}$. Then by this assumption that P(j-1) can be written as $\displaystyle 7(5^{k-1}-2^{k-1})-10(5^{k-2}-2^{k-2})$

Now I'm kind of stuck. This is either going to take some sick algebra or I made a boo-boo.

Under the assumption $\displaystyle b_k = 5^k - 2^k$:

$\displaystyle b_{k+1} = 7b_k - 10b_{k-1} = 7(5^k - 2^k) - 10(5^{k-1} - 2^{k-1})$

$\displaystyle = 5^{k-1}(7 \times 5 - 10) - 2^{k-1}(7 \times 2 - 10) = 25 \times 5^{k-1} - 4 \times 2^{k-1} = 5^{k+1} - 2^{k+1}$.

And it's blue sky all the way ......

Originally Posted by mr fantastic

Under the assumption $\displaystyle b_k = 5^k - 2^k$:

$\displaystyle b_{k+1} = 7b_k - 10b_{k-1} = 7(5^k - 2^k) - 10(5^{k-1} - 2^{k-1})$

$\displaystyle = 5^{k-1}(7 \times 5 - 10) - 2^{k-1}(7 \times 2 - 10) = 25 \times 5^{k-1} - 4 \times 2^{k-1} = 5^{k+1} - 2^{k+1}$.

And it's blue sky all the way ......

Very nice! Thank you Only question is about "Under the assumption $\displaystyle b_k = 5^k - 2^k$:" We assumed that P(j) for all j<k so it's safe to assume this?

EDIT: On second thought, maybe just writing that in terms of j+1 would be better? I'm not 100% sure. I get the proof. My teacher is just a major nitpicker with tiny details.

Originally Posted by Jameson

Very nice! Thank you Only question is about "Under the assumption $\displaystyle b_k = 5^k - 2^k$:" We assumed that P(j) for all j<k so it's safe to assume this?

EDIT: On second thought, maybe just writing that in terms of j+1 would be better? I'm not 100% sure. I get the proof. My teacher is just a major nitpicker with tiny details.

Well, I think it's as simple as:

Step 1: Show P(2) true. Done.

Step 2: Assume true for n = k, that is, assume P(k) true for n = k. This is the inductive hypothesis. Done.

Step 3: Show P(k+1) true follows from P(k) true. Done.

Therefore, etc. etc.

You're absolutely right. The text we have for some reason makes a case for two types of induction, the first one as you just described and the second one like this:

"Suppose for each number, n, P(n) is a statement associated with n and the statement has the following properties:

a)If P(k) is true whenever P(j) holds for all natural numbers j<k, then P(n) holds for all natural numbers n."

This is essentially the same method, but for some reason when we reference the induction hypothesis we must pick one of the two. My teacher is kind of strange. But I got the proof now. Thank you very much!