Determine the exact formula for the following discrete models:

2tn+2 = 3tn+1 + 2tn; t0 = 1; t1 = 3;

49yn+2 = -16yn; y0 = 0; y1 = 2;

9xn+2 = 12xn+1- 85xn; x0 = 0; x1 =1

Respuesta :

I'm partial to solving with generating functions. Let

[tex]T(x)=\displaystyle\sum_{n\ge0}t_nx^n[/tex]

Multiply both sides of the recurrence by [tex]x^{n+2}[/tex] and sum over all [tex]n\ge0[/tex].

[tex]\displaystyle\sum_{n\ge0}2t_{n+2}x^{n+2}=\sum_{n\ge0}3t_{n+1}x^{n+2}+\sum_{n\ge0}2t_nx^{n+2}[/tex]

Shift the indices and factor out powers of [tex]x[/tex] as needed so that each series starts at the same index and power of [tex]x[/tex].

[tex]\displaystyle2\sum_{n\ge2}2t_nx^n=3x\sum_{n\ge1}t_nx^n+2x^2\sum_{n\ge0}t_nx^n[/tex]

Now we can write each series in terms of the generating function [tex]T(x)[/tex]. Pull out the first few terms so that each series starts at the same index [tex]n=0[/tex].

[tex]2(T(x)-t_0-t_1x)=3x(T(x)-t_0)+2x^2T(x)[/tex]

Solve for [tex]T(x)[/tex]:

[tex]T(x)=\dfrac{2-3x}{2-3x-2x^2}=\dfrac{2-3x}{(2+x)(1-2x)}[/tex]

Splitting into partial fractions gives

[tex]T(x)=\dfrac85\dfrac1{2+x}+\dfrac15\dfrac1{1-2x}[/tex]

which we can write as geometric series,

[tex]T(x)=\displaystyle\frac8{10}\sum_{n\ge0}\left(-\frac x2\right)^n+\frac15\sum_{n\ge0}(2x)^n[/tex]

[tex]T(x)=\displaystyle\sum_{n\ge0}\left(\frac45\left(-\frac12\right)^n+\frac{2^n}5\right)x^n[/tex]

which tells us

[tex]\boxed{t_n=\dfrac45\left(-\dfrac12\right)^n+\dfrac{2^n}5}[/tex]

# # #

Just to illustrate another method you could consider, you can write the second recurrence in matrix form as

[tex]49y_{n+2}=-16y_n\implies y_{n+2}=-\dfrac{16}{49}y_n\implies\begin{bmatrix}y_{n+2}\\y_{n+1}\end{bmatrix}=\begin{bmatrix}0&-\frac{16}{49}\\1&0\end{bmatrix}\begin{bmatrix}y_{n+1}\\y_n\end{bmatrix}[/tex]

By substitution, you can show that

[tex]\begin{bmatrix}y_{n+2}\\y_{n+1}\end{bmatrix}=\begin{bmatrix}0&-\frac{16}{49}\\1&0\end{bmatrix}^{n+1}\begin{bmatrix}y_1\\y_0\end{bmatrix}[/tex]

or

[tex]\begin{bmatrix}y_n\\y_{n-1}\end{bmatrix}=\begin{bmatrix}0&-\frac{16}{49}\\1&0\end{bmatrix}^{n-1}\begin{bmatrix}y_1\\y_0\end{bmatrix}[/tex]

Then solving the recurrence is a matter of diagonalizing the coefficient matrix, raising to the power of [tex]n-1[/tex], then multiplying by the column vector containing the initial values. The solution itself would be the entry in the first row of the resulting matrix.

ACCESS MORE
ACCESS MORE
ACCESS MORE
ACCESS MORE