Let $T_1 = 1$, $T_2 = 2$ and $T_n = (T_{n−1} + T_{n−2})/2$ when $n ≥ 3$. Find a closed form expression for $T_n$ that applies when $n ≥ 3.$

Question

Having trouble finding a closed form expression that applies for all $n$. I tried looking at $T_3, T_4, T_5,$ and $T_6$ to see some pattern but found none. Is there a kind of trick for these problems?

Answer 1

One way to solve such a recurrence relation is to find roots of the characteristic equation,

which in this case is $x^2=(x+1)/2$, so the roots are $1$ and $-\frac12$,

so $T_n=A+B\left(-\frac12\right)^n$. Use the fact that $T_1=1$ and $T_2=2$ to solve for $A$ and $B$.