Add Me!Close Menu Navigation

More Linear Recurrences

Let (x_n )_n = 0 be defined by the recurrence relation x_{n + 1} = ax_n + bx_{n - 1}, with x_0 = 0. Show that the expression x^2_n - x_{n - 1} x_{n + 1} depends only on b and x_1, but not on a.

In order to do this problem, we will first prove a few trivial properties of its system first.

x_n is linear in x_1

We show this inductively on the naturals. Suppose P_n \equiv x_n = c_n x_1, then, we show P_{k-2},P_{k-1} \implies P_k

    \begin{align*} x_{k+1} &= ax_k + bx_{k-1} & P_{k-1},P_k \\ &= c_k x_1 + c_{k-1} x_1 \\ &= (c_k + c_{k-1}) x_1 \\ &= c_{k+1} x_1 \\ &\implies P_{k+1} \end{align*}

This concludes our proof that x_n = c_n x_1 for some number c_n, and is hence linear in x_1. \blackbox

Therefore x_n^2 - x_{n-1}x_{n+1} = C x_1^2, and without loss of generality, we can replace x_1 with any arbitrary number. We will pick x_1 = 1 for the sake of simplicity.

Guess and check

Let’s generate a few numbers for x_n with x_1 = 1

    \[\begin{tabular}{c | c | c} n & x_n & x_n^2 - x_{n-1}x_{n+1} \\ \hline 0 & 0 & \varnothing\\ 1 & 1 & 1\\ 2 & a & a^2 - a^2 - b = -b\\ 3 & a^2 + b & a^4 + 2a^2b + b^2 - a^4 - 2a^2b = b^2\\ 4 & a^3 + 2ab & -b^3 \\ \vdots & \vdots & \vdots \end{tabular}\]

This naturally suggests that

(1)   \begin{equation*} x_n^2 - x_{n-1}x_{n+1} = (-b)^n \end{equation*}

Show that x_n^2 - x_{n-1}x_{n+1} = (-b)^n

We will prove this via induction on the naturals. Let P_n \equiv x_n^2 - x_{n-1}x_{n+1} = (-b)^n, then from the table above, it is obvious that P_1,P_2 holds. We will now show that P_k \implies P_{k+1}. Informally, we will expand the x_{k+2} term within the first order recursive expansion of x_{k+1} along with the equivalent construct x_k^2 = (-b)^k + x_{k-1}x_{k+1}. The body of the induction is as follows:

    \begin{align*} x_{k+1} &= x_{k+1}^2 - x_kx_{k+1} \\ &= x_{k+1}^2 - x_k(bx_k + ax_{k+1}) \\ &= x_{k+1}^2 - bx_k^2 - ax_{k+1}x_k \\ &= x_{k+1}^2 - b\left((-b)^k + x_{k-1}x_{k+1}\right)  - ax_{k+1}x_k & P_k \\ &= x_{k+1}^2 + (-b)^{k+1} - bx_{k-1}x_{k+1} - ax_{k+1}x_k \\ &= x_{k+1}^2 + (-b)^{k+1} - x_{k+1}(bx_{k-1} + ax_{k}) \\ &= x_{k+1}^2 + (-b)^{k+1} - x_{k+1}(x_{k+1}) \\ &= (-b)^{k+1} \\ &\implies P_{k+1} \end{align*}

This concludes our proof that x_n^2 - x_{n-1}x_{n+1} = (-b)^n and the proof that x_n^2 - x_{n-1}x_{n+1} does not depend on a. \blacksquare

Posted By Lee

Woosh

Recent Comments