## Linear recurrences

### Task number: 3874

Find the formula (the analytical expression) for the \(n\)-th element of the sequence specified by the following recurrences:

#### Variant

\(a_0=1, a_{n+1}=a_n+1\)

#### Solution

Although the solution is obvious, we illustrate on this task the general procedure for solving recurrences.

We find the generating function for the sequence \((a_0,a_1,a_2,…)\) and get \(a(x)=xa(x)+\frac{1}{1-x}\).

The term \(xa(x)\) corresponds to the expression \(a_{n}\) on the right-hand side of the description of \(a_{n+1}\). The function \(\frac{1}{1-x} \) corresponds to the sequence of all ones, which corresponds to the addition of 1 on the right-hand side of the formula for \(a_{n+1}\).

The desired function is \(a(x)=\frac{1}{(1-x)^2}\) and it corresponds to the sequence \( (1{,}2,3,…)\).¨

#### Variant

\(a_0=1, a_{n+1}=2a_n+3\)

#### Solution

We compile a generating function for the sequence \((a_0,a_1,a_2,…)\) and we get \(a(x)=2xa(x)+\frac{3}{1-x}-2\).

The term \(2xa(x)\) corresponds to the expression of \(2a_{n}\) in the right-hand of the recurrence for \(a_{n+1}\). The function \(\frac{3}{1-x}-2\) corresponds to the sequence \((1{,}3,3{,}3,…)\), the elements of which are gradually added to the right-hand side of the recurrence for \(a_{n+1}\).

The final generating function is \(a(x)=\frac{1}{1-2x}\left(\frac{3}{1-x}-2\right)\).

In order to obtain the analytical expression, it is necessary to iteratively derive \(a(x)\), in other words, construct the corresponding Taylor series. For this, the decomposition of \(a(x)\) into partial fractions is used. In our case, in has the form \(\frac{\alpha}{1-\lambda_1x}+\frac{\beta}{1-\lambda_2x}\).

Note that the left summand of the decomposition is the generating function for \((\alpha,\alpha\lambda_1,\alpha\lambda_1^2,\alpha\lambda_1^3,…)\) and the right summand \((\beta,\beta\lambda_2,\beta\lambda_2^2,…)\) therefore the \(n\)-th element of the sequence can be immediately expressed as \(a_n=\alpha\lambda_1^n+\beta\lambda_2^n\).

By comparing the denominators in \(a(x)\) and in the searched decomposition we get \(\lambda_1=1\) and \(\lambda_2=2\).

The coefficients \(\alpha\) and \(\beta\) are calculated from a linear system of equations whose rows correspond to the equations for \(a_0\) and \(a_1\):

\(a_0=1=\alpha 1^0+\beta2^0=\alpha+\beta\\ a_1=5=\alpha 1^1+\beta2^1=\alpha+2\beta\)

hence \(\alpha=-3\) a \(\beta=4\).#### Answer

The sequence can be obtained by the formula \(a_n=2^{n+2}-3\).

#### Variant

\(a_0=a_1=1, a_{n+2}=a_{n+1}+6a_n\)

#### Hint

Comments to simplify the procedure in the general case:

Non-homogeneous recurrences of type \(a_n=q_1a_{n-1}+q_2a_{n-2}+…+q_ka_{n-k}+b\) yield in the generating function always the term \(\frac{b}{1-x}\). The presence of this term causes that some power of the root of the polynomial \(1-x\) always appears in the analytical expression (possibly with the appropriate multiplicity as in the previous variant). This root is denoted by \(\lambda_0=1 \) in the following tasks.

The other \(\lambda_1,…,\lambda_k\) are calculated from the homogeneous recurrence \(a_n=q_1a_{n-1}+q_2a_{n-2}+…+q_ka_{n-k}\) as roots of the so-called characteristic polynomial \(y^k-q_1y^{k-1}-q_2y^{k-2}-…-q_k\).

The explanation for this phenomena follows. If we look for a decomposition,

\(1-q_1x-q_2x^2-…-q_kx^k=(1-\lambda_1x)(1-\lambda_2x)…(1-\lambda_kx)\)

we can multiply the whole equation by \(y^k\) for \(y=\frac1x\) and get:

\(y^k-q_1y^{k-1}-q_2y^{k-2}-…-q_ky^0=(y-\lambda_1)(y-\lambda_2)…(y-\lambda_k)\).

Thus \(\lambda_i\) is a suitable coefficient in decomposition if and only if it is the root of the characteristic polynomial.

If \(\lambda_i \) is a root of multiplicity \(k\), then the decomposition into partial fractions contains factors with \((1-\lambda_i)^l\), for \(l=1,…,k\) in the denominators. Then, the analytical expression contains terms \(n^{l-1}\lambda_i^n\).

#### Solution

The charakteristic polynomial \(\lambda^2-\lambda-6 = (\lambda+2) (\lambda-3)\) has roots

\(\lambda_1=-2, \lambda_2=3\), tedy \(a_n=\alpha (-2)^n + \beta 3^n\).

We substitute for \(n=0{,}1\):

\( 1 = \alpha+\beta \\ 1 = -2\alpha+3\beta \)

and get \(\alpha=\frac{2}{5}, \beta=\frac{3}{5}\).

#### Answer

The sequence can be obtained by the formula \(a_n=\frac{2}{5} (-2)^n + \frac{3}{5}\; 3^n\).

#### Variant

\(a_0=a_1=1, a_{n+2}=a_{n+1}+6a_n-4\)

#### Solution

Due to the inhomogeneity of the difference equation, we add to the roots of the previous solution also the “root” \(\lambda_0=1\). We obtain \(a_n=\alpha (-2)^n + \beta 3^n+\gamma\).

From the rekurence de calculate \(a_2= 3\). Now for \(n=0{,}1,2\) we get the system:

\( 1= \alpha+\beta+\gamma \\ 1 = -2\alpha+3\beta+\gamma \\ 3 = 4\alpha+9\beta+\gamma \)

This system has solution \(\alpha=\frac{2}{15}, \beta=\frac{1}{5}, \gamma=\frac{2}{3}\).

#### Answer

The sequence can be obtained by the formula \(a_n=\frac{2}{15} (-2)^n + \frac{1}{5}\; 3^n+\frac{2}{3}\).

#### Variant

\(a_0=0, a_1=1, a_{n+2}=4(a_{n+1}-a_n)\)

#### Solution

Now the charakteristic polynomial \(\lambda^2-4\lambda+4=(\lambda-2)^2\) yields a root of multiplicity two \(\lambda_{1{,}2}=2\). In the decomposition into partial fractions, it is therefore necessary to add a fraction with a denominator in the second power. Thus, in the sequence a term of the form \(n\lambda^n\).

Thus \(a_n=\alpha 2^n+\beta n 2^n\). For \(n=0{,}1\) we obtain the system

\( 0=\alpha \\ 1=2\alpha+2\beta \)

with solution \(\alpha=0, \beta=\frac{1}{2}\).

#### Answer

The sequence can be obtained by the formula \(a_n=n\ 2^{n-1}\).

#### Variant

\(a_0=0, a_1=1, a_{n+2}=4(a_{n+1}-a_n)+1\)

#### Solution

Again, it suffices to add the root \(\lambda_0=1\), determine \(a_2=5\) and solve the system:

\( 0=\alpha+\gamma \\ 1=2\alpha+2\beta+\gamma \\ 5=4\alpha+8\beta+\gamma \)

It has solution \(\alpha=1, \beta=-1, \gamma=1\).

#### Answer

The sequence can be obtained by the formula \(a_n=1+(n-1)2^n\).

#### Variant

\(a_0=2, a_1=3, a_{n+2}=3a_n-2a_{n+1}\)

#### Answer

The sequence can be obtained by the formula \(a_n=\frac{9-(-3)^n}{4}\).

#### Variant

\(a_0=0, a_1=1, a_{n+2}=a_{n+1}+2a_n+2\)

#### Answer

The sequence can be obtained by the formula \(a_n=2^n-1\).

#### Variant

\(a_0=a_1=1, 5a_{n+2}=4a_{n+1}-a_n\)

#### Variant

\(a_0 = 4, a_1 = 3, a_n = a_{n-1} + 2 a_{n-2} + 3{\cdot} 2^n\) for \(n \geq 2\)

#### Hint

This is a more difficult option. Try to solve the recurrence by use of generating functions.

#### Answer

The sequence can be obtained by the formula \((2n + 1)2^n + 3\cdot(-1)^n\).