A sequence is defined by a1 6 a2 22 and an 6an1 7an2 for

A sequence is defined by a₁ = 6, a₂ = 22 and a_n = 6a_n1 7a_n2 for each integer n 3. Using strong induction, prove that an = (3+ 2)ⁿ + (3 2)ⁿ for every positive integer n.

Solution

We will prove by strong induction that, for all n N,

() an = (3+ 2)n + (3 2)n .

Base case:

When n = 1, the left side of () is a1 = 6, and the right side is (3+ 2).1 + (3 2).1 = 6, so both sides are equal and () is true for n = 1.

When n = 2, the left and right sides of () are a2 = 12(It should be 12**) and (3+ 2).2 + (3 2).2 = 12, so () holds in this case as well.

Induction step: Let k N with k 2 be given and suppose () is true for n = 1, 2, . . . , k. Then

a_k+1 = 6ak - 7ak1 (by recurrence for an) = 6[(3+ 2)k + (3 2)k]-7[(3+ 2)(k-1) + (3 2)(k-1)]

(by () for n = k and n = k 1)

= (3+ 2)(k+1) + (3 2)(k+1) (by algebra).

Thus, () holds for n = k + 1, and the proof of the induction step is complete. Conclusion: By the strong induction principle, it follows that () is true for all n N.