1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Toby Mak Nov 2 '17 at 5:15
  • $\begingroup$ Is my solution the same as the explicit formula for this recurrence relation? $\endgroup$ – smith1453 Nov 2 '17 at 5:19
  • $\begingroup$ @smith1453 Welcome to MSE! Here you are able to use MathJax which is an excellent language for writting mathematical expressions. $\endgroup$ – mucciolo Nov 2 '17 at 5:32
1
$\begingroup$

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.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.