Problem set 5: Linear Recurrence Relations

1 Linear Recurrence Relations

1.1 Definition: Linear Recurrence Relations

A sequence \((a_n)_{n\geq 0}\) satisfies a linear recurrence relation of order \(k\) if there exist constants

\[ \alpha_1,\ldots,\alpha_k, \qquad \alpha_k\neq 0, \]

such that

\[ a_{n+k} = \alpha_1a_{n+k-1} +\alpha_2a_{n+k-2} +\cdots+ \alpha_ka_n \]

for every \(n\geq 0\).

The polynomial

\[ p(x)=x^k-\alpha_1x^{k-1}-\cdots-\alpha_k \]

is called the characteristic polynomial of the recurrence.

Recall that a number \(r\) is a root of a polynomial \(p(x)\) of multiplicity \(l\) if \((x-r)^l\) divides \(p(x)\), but \((x-r)^{l+1}\) does not.

1.2 Theorem: General Solution of a Linear Recurrence

Suppose the characteristic polynomial has distinct roots

\[ r_1,\ldots,r_m \]

with multiplicities

\[ l_1,\ldots,l_m, \]

respectively.

Then every solution of the recurrence has the form

\[ \boxed{ a_n=P_1(n)r_1^n+\cdots+P_m(n)r_m^n, } \]

where each \(P_i(n)\) is a polynomial of degree at most \(l_i-1\).

1.3 Problems

Find the general solution of each of the following linear recurrence relations.

(a)

\[ a_{n+2}-7a_{n+1}+12a_n=0. \]

(b)

\[ a_{n+3}-2a_{n+2}-4a_{n+1}+8a_n=0. \]

(c)

\[ a_{n+2}+a_{n+1}+a_n=0. \]

(d)

\[ a_{n+2}-9a_n=0. \]

(e)

\[ a_{n+3}+3a_{n+2}+3a_{n+1}+a_n=0. \]

(f)

\[ a_{n+3}-5a_{n+2}+12a_{n+1}-8a_n=0. \]

Find a homogeneous linear recurrence relation with constant coefficients satisfied by the sequence \((a_n)\) in each of the following cases.

(a)

\[ a_{n+2}=a_{n+1}+a_n+1. \]

(b)

\[ a_{n+2}=2a_{n+1}-a_n+n+1. \]

(c)

\[ a_{n+2}=a_{n+1}+6a_n+3^n. \]

1.4 Fibonacci Numbers

The Fibonacci sequence \((F_n)_{n\geq 0}\) is defined by

\[ F_0=0,\qquad F_1=1, \]

and

\[ F_n=F_{n-1}+F_{n-2}, \qquad n\geq 2. \]

Find an explicit formula for the \(n\)-th Fibonacci number \(F_n\).

Find explicit formulas for the following sums of Fibonacci numbers.

(a)

\[ F_0+F_1+\cdots+F_n. \]

(b)

\[ F_0^2+F_1^2+\cdots+F_n^2. \]

(c)

\[ F_0^3+F_1^3+\cdots+F_n^3. \]

Let \(A_n\) denote the number of ways to tile a given region.

Find a recurrence relation for \(A_n\) in each of the following cases.

(a) Tiling an \(n\times 3\) rectangle using \(1\times 2\) dominoes.

(b) Tiling an \(n\times 4\) rectangle using \(1\times 2\) dominoes.

(c) Tiling a \(2\times 2\times n\) rectangular prism using \(2\times 1\times 1\) bricks.

In each case, the tiles must cover the region completely, without gaps or overlaps.

How many sequences of length \(n\) can be formed using the following alphabets if no two zeros are adjacent?

(a)

\[ \{0,1\}. \]

(b)

\[ \{0,1,2\}. \]

Let \(k\geq 1\) be a fixed integer.

Prove that the sequence

\[ a_n=n^{k-1} \]

satisfies the recurrence relation

\[ \boxed{ a_{n+k} - \binom{k}{1}a_{n+k-1} + \binom{k}{2}a_{n+k-2} -\cdots+ (-1)^k\binom{k}{k}a_n =0. } \]

Consider a hexagon \(ABCDEF\).

A frog is initially located at vertex \(B\).

Every second, the frog jumps to one of the two neighboring vertices of the hexagon.

How many different ways can the frog reach vertex \(A\) in exactly \(n\) jumps?

Consider the sequence \((a_n)\) defined by

\[ a_{n+2}+a_{n+1}+2a_n=0, \]

with initial conditions

\[ a_1=1, \qquad a_2=-1. \]

Prove that, for every positive integer \(n\), the number

\[ \boxed{ 2^{n+2}-7a_n^2 } \]

is a perfect square.

Consider a chessboard of size \(1000\times 3\).

A chess king is initially located in the middle square of the leftmost column.

How many different ways can the king reach the rightmost column in exactly \(999\) moves?

The king moves according to the usual chess rules: in one move, it can move to any horizontally, vertically, or diagonally adjacent square.