# Quod Erat Demonstrandum

## 2009/01/02

### Something about F.6 Pure Math First Term Exam

Filed under: HKALE,Pure Mathematics — johnmayhk @ 4:24 下午
Tags: ,

Here is one of questions:

Given that

$x_1 = 4, x_2 = 12$
$x_{n + 2} = 4(x_{n + 1} - x_{n})$ ($\forall n \in \mathbb{N}$)

Prove that

(a) $x_n = 2(1 + \frac{1}{n})x_{n - 1}$
(b) $x_n = (n + 1)2^n$

The question requires students to use mathematical induction to prove that.

I’d like to give another ways.

(method 1)

By looking at $x_{n + 2} - 4x_{n + 1} + 4x_{n} = 0$, we can solve $x_n$ just like what we do in solving second order linear differential equation. What? Urm, the characteristic equation is

$\lambda^2 - 4\lambda + 4 = 0$

Yield, $\lambda = 2$ (repeated)

Hence,

$x_n = (An + B)(2^n)$

With initial conditions $x_1 = 4$ and $x_2 = 12$, we have

$2(A + B) = 4 \Rightarrow A + B = 2$
$4(2A + B) = 12 \Rightarrow 2A + B = 3$

On solving, $A = B = 1$, thus

$x_n = 2^n(n + 1)$

(method 2)

The simplicity of the method 1 is actually the result of iteration, let’s present it more explicitly.

$x_{n + 2} = 4(x_{n + 1} - x_{n})$
$x_{n + 2} - 2x_{n + 1} = 2(x_{n + 1} - 2x_{n})$ – – – – – – (*)

Now apply (*) again and again,

$x_{n + 2} - 2x_{n + 1}$
$= 2(x_{n + 1} - 2x_{n})$ [by (*)]
$= 2^2(x_{n} - 2x_{n - 1})$ [by (*)]
$= 2^3(x_{n - 1} - 2x_{n - 2})$ [by (*)]
. . . inductively . . .
$= 2^n(x_{2} - 2x_{1})$ [by (*)]

Thus,

$x_{n + 2} = 2x_{n + 1} + 2^{n + 2}$ – – – – – – (#)
($\because x_1 = 4, x_2 = 12$)

Now we apply (#) again and again,

$x_{n + 2}$
$= 2x_{n + 1} + 2^{n + 2}$ [by (#)]
$= 2(2x_n + 2^{n + 1}) + 2^{n + 2}$ [by (#)]
$= 2^2x_n + 2(2^{n + 2})$
$= 2^2(2x_{n - 1} + 2^{n}) + 2(2^{n + 2})$ [by (#)]
$= 2^3x_{n - 1} + 3(2^{n + 2})$
. . . inductively. . .
$= 2^{n + 1}x_1 + (n + 1)2^{n + 2}$
$= 2^{n + 3} + (n + 1)2^{n + 2}$ ($\because x_1 = 4$)

Hence

$x_{n + 2} = 2^{n + 3} + (n + 1)2^{n + 2}$
$x_{n} = 2^{n + 1} + (n - 1)2^{n}$ (replace $n$ by $n - 2$)

Therefore

$x_n = 2^n(n + 1)$

## 2 則迴響 »

1. 有少許簡單複雜化的感覺…
不過我諗Nelson Sir的原意是想考我們能否看到要轉subject去做assumption而已…
結果一條F.4 standard的數就考起了很多人…(包括我=.=")

迴響 由 Patrick Wong — 2009/01/02 @ 11:36 下午 | 回應

2. Patrick, 是簡單複雜化了，用 M.I. 當然可以啦，但我其實是想，出題者究竟是如何擬出這題？

迴響 由 johnmayhk — 2009/01/03 @ 9:07 下午 | 回應