Given a sequence defined recursively and its closed form, use strong mathematical induction to prove that the definitions are equivalent.

Question

Suppose that a0, a1, a2, . . . is a sequence defined as follows:

a0 = 2, a1 = 1, an = an−1 + 12an−2 for every integer n ≥ 2.

Prove that an = (−3)n + 4n for every integer n ≥ 0.\

p(0): (-3)^0+4^0= 2

p(1): (-3)^1+4^1=1

so true

Inductive step:

Suppose that ai=(-3)^i+4^i for every integer i from 0 through k, for some integer k>1.

In particular, ak-1=(-3)^k-1 + 4^k-1 and ak=(-3)^k + 4^k. Since k>1, we have k+1>2, and therefore

ak+1=an+ 12an-1 by given recurrence relation

((-3)^k+4^k) + 12((-3)^k-1 +4^k-1)

-3^k+4^k + 12*-3^k-1 + 12*4^k-1

-4*-3*-3^k-1+ 3*4*4^k-1

- 4*-3^k + 3*4^k

(-3^k+4^k) + (-4*-3^k + 3*4^k)

I got this far, but this doesn't seem right.

Answer 1

Base case: If n=0, then a_0=(-3)^0+4^0=2 which matches the given a_0=2.

Inductive hypothesis: Assume a_n=(-3)^n+4^n holds for every n.

Prove the n+1 case: We have a_{n+1}=a_n+12a_{n-1}=(-3)^n+4^n+12((-3)^{n-1}+4^{n-1})=(-3)^n+4^n+12(-3)^{n-1}+12(4)^{n-1}=(-3)^n+4^n-(-12)(-3)^{n-1}+12(4)^{n-1}=(-3)^n+4^n-(4)(-3)^{n}+(3)(4)^{n}=(-3)^n-4(-3)^n + 4^n+(3)4^n= -3(-3)^n+4(4)^n=(-3)^{n+1}+4^{n+1}, thus proving the n+1 case, finishing induction.

It's hard to write in text, so feel free to reach out, but that is the answer.