[SOLVED] Recursive sequence induction proof

**Jameson** · Feb 21st 2008, 08:09 PM

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

Proof:

Let P(n) be the propositional statement for n>1 " $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 $5^j-2^j=7b_{j-1}-10b_{j-2}$ . Then by this assumption that P(j-1) can be written as $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.

**mr fantastic** · Feb 21st 2008, 08:23 PM

Originally Posted by Jameson

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

Proof:

Let P(x) be the propositional statement for n>1 " $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 $5^j-2^j=7b_{j-1}-10b_{j-2}$ . Then by this assumption that P(j-1) can be written as $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 $b_k = 5^k - 2^k$ :

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

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

**Jameson** · Feb 21st 2008, 08:37 PM

Originally Posted by mr fantastic

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

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

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

**mr fantastic** · Feb 21st 2008, 09:38 PM

Originally Posted by Jameson

Very nice! Thank you

Only question is about "Under the assumption $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.

**Jameson** · Feb 21st 2008, 11:04 PM

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!

Thread: [SOLVED] Recursive sequence induction proof

LinkBack

Thread Tools

Display

[SOLVED] Recursive sequence induction proof

Similar Math Help Forum Discussions

[SOLVED] Proof a recursive formula with induction

[SOLVED] Fibonacci sequence induction proof

Proof of Convergence for Recursive Sequence

[SOLVED] Recursive sequence and primes

[SOLVED] help with writing a recursive formula for a sequence

Search Tags