Science:Math Exam Resources/Courses/MATH307/April 2009/Question 07 (a)/Solution 1

We can start by finding the first few values of this relation. $x_{2} = 3 b - 2 a$ $x_{3} = 7 b - 6 a$ $x_{4} = 15 b - 14 a$ $x_{5} = 31 b - 30 a$ With these, we can guess at a scalar expression for $x_{n}$ and then use induction to prove that it is correct. By inspection, we come up with the following:

$x_{n} = (2^{n} - 1) b - (2^{n} - 2) a$ .

Proof: $n = 0$ : $x_{0} = (2^{0} - 1) b - (2^{0} - 2) a = 0 b - (- 1) a = a$ $n = 1$ : $x_{1} = (2^{1} - 1) b - (2^{1} - 2) a = 1 b - 0 a = b$ $n = 2$ : $x_{2} = (2^{2} - 1) b - (2^{2} - 2) a = (4 - 1) b - (4 - 2) a = 3 b - 2 a$ , which is what we found using the recurrence.

Assume that for $n \leq k$ , the expression is true.

We now want to prove that the expression is true for $n = k + 1$ . Using the recurrence relation and our induction hypothesis, we find that $x_{k + 1} = 3 x_{k} - 2 x_{k - 1}$ $= 3 ((2^{k} - 1) b - (2^{k} - 2) a) - 2 ((2^{k - 1} - 1) b - (2^{k - 1} - 2) a)$ $= b (3 (2^{k} - 1) - 2 (2^{k - 1} - 1)) - a (3 (2^{k} - 2) - 2 (2^{k - 1} - 2))$ $= b (2^{k} (3 - 1) - 3 + 2) - a (2^{k} (3 - 1) - 2)$ $= b (2^{k + 1} - 1) - a (2^{k + 1} - 2)$ , which is the expression we had come up with. So for all integers n, $x_{n} = (2^{n} - 1) b - (2^{n} - 2) a$ .