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

I'm partial to solving with generating functions. Let

Multiply both sides of the recurrence by and sum over all .

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

Now we can write each series in terms of the generating function . Pull out the first few terms so that each series starts at the same index .

Solve for :

Splitting into partial fractions gives

which we can write as geometric series,

which tells us

# # #

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

By substitution, you can show that

or

Then solving the recurrence is a matter of diagonalizing the coefficient matrix, raising to the power of , 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.

"if it is my birthday, then it is snowing"