# Explicit Formula for a Linear Homogeneous Recurrence Relation

Is finding the explicit formula for a linear homogeneous recurrence relation the same process as solving for the linear homogeneous recurrence relation? For example, if I solved:

$$b_n = b_{n−1} + 12 b_{n−2}$$ with initial values $b_0 = −2$ and $b_1 = 20$.

Would the solution $b_n = 2 \cdot 4^n - 4(-3)^n$ be the explicit formula?

• According to Wolfram Alpha, the solution is $2^{2n+1}-4(-3)^n$. However, since $2^{2n+1} = 2*4^n$, your solution is correct. – Toby Mak Nov 2 '17 at 5:15
• Is my solution the same as the explicit formula for this recurrence relation? – smith1453 Nov 2 '17 at 5:19
• @smith1453 Welcome to MSE! Here you are able to use MathJax which is an excellent language for writting mathematical expressions. – mucciolo Nov 2 '17 at 5:32

Let $B(z) = \sum_{n=0}^\infty b_nz^n$. Multiplying both sides of the recurrence by $z^n$ and summing over $n\geqslant 2$ yields $$\sum_{n=2}^\infty b_nz^n = \sum_{n=2}^\infty b_{n-1}z^n + 12\sum_{n=2}^\infty b_{n-2}z^n.\tag1$$ Writing $(1)$ in terms of $B(z)$, we have $$B(z) - b_0 - b_1z = z(B(z) - b_0) + 12z^2B(z).\tag2$$ Substituting $b_0=-$2 and $b_1=20$ into $(2)$ and solving for $B(z)$, we have $$B(z) = \frac{-2+11z}{1-z-12z^2}\tag3$$ Using partial fraction decomposition, we may write the RHS of $(3)$ as $$-4\left(\frac1{1+3z}\right)+2\left(\frac1{1-4z}\right),\tag4$$ and expanding $(4)$ as a power series yields $$B(z) = \sum_{n=0}^\infty\left(4(-1)^{n+1}3^n + 2\cdot 4^n \right)z^n.$$ It follows that $$b_n = 4(-1)^{n+1}3^n + 2\cdot 4^n,\ n\geqslant2.$$