<s>[INST] Solve recursion $a_{n}=ba_{n-1}+cd^{n-1}$ Let $b,c,d\in\mathbb{R}$ be constants with $b\neq d$. Let
$$\begin{eqnarray}
a_{n} &=& ba_{n-1}+cd^{n-1}
\end{eqnarray}$$
be a sequence for $n \geq 1$ with $a_{0}=0$. I want to find a closed formula for this recursion. (I only know the german term geschlossene Formel and translated it that way I felt it could be right. So if I got that wrong, please correct me)
First I wrote down some of the chains and I got
$$\begin{eqnarray}
a_{n} &=& ba_{n-1}+cd^{n-1}\\
&=& b\left(ba_{n-2}+cd^{n-2}\right)+cd^{n-1}\\
&=& b\left(b\left(ba_{n-3}+cd^{n-3}\right)+cd^{n-2}\right)+cd^{n-1}\\
&=& b\left(b\left(b\left(ba_{n-4}+cd^{n-4}\right)+cd^{n-3}\right)+cd^{n-2}\right)+cd^{n-1}\\
&=& \dots\\
&=& \sum_{k=0}^{n}b^{k}cd^{n-k-1}\\
&=& \sum_{k=0}^{n}b^{k}cd^{n-\left(k+1\right)}
\end{eqnarray}$$
So I catched the structure in a serie. Now I am asking myself how to proceed. I took the liberty to have a little peek at what WolframAlpha wood say to this serie. I hoped for inspiration and I got
$$\sum_{k=0}^{n-1}b^{k} c d^{n-(k+1)} = (c (b^n-d^n))/(b-d)$$
How did this came to be? And more important: Is my approach useful?
Thank you in advance for any advice!
Edit: My final Solution (recalculated)
$$\begin{eqnarray}
a_{n} &=& ba_{n-1}+cd^{n-1}\\
&=& b\left(ba_{n-2}+cd^{n-2}\right)+cd^{n-1}\\
&=& b\left(b\left(ba_{n-3}+cd^{n-3}\right)+cd^{n-2}\right)+cd^{n-1}\\
&=& b\left(b\left(b\left(ba_{n-4}+cd^{n-4}\right)+cd^{n-3}\right)+cd^{n-2}\right)+cd^{n-1}\\
&=& b^{4}a_{n-4}+b^{3}cd^{n-4}+b^{2}cd^{n-3}+bcd^{n-2}+cd^{n-1}\\
&=& b^{5}a_{n-5}+b^{4}cd^{n-5}+b^{3}cd^{n-4}+b^{2}cd^{n-3}+bcd^{n-2}+cd^{n-1}\\
&=& b^{n}a_{0}+b^{n-1}c+\dots+b^{4}cd^{n-5}+b^{3}cd^{n-4}+b^{2}cd^{n-3}+cbd^{n-2}+cd^{n-1}\\
&=& \dots\\
&=& 0+b^{n-1}c+\dots+b^{4}cd^{n-5}+b^{3}cd^{n-4}+b^{2}cd^{n-3}+cbd^{n-2}+cd^{n-1}\\
&=& \sum_{k=0}^{n-1}b^{k}cd^{n-1-k}\\
&=& cd^{n-1}\sum_{k=0}^{n-1}b^{k}d^{-k}\\
&=& cd^{n-1}\sum_{k=0}^{n-1}\left(\frac{b}{d}\right)^{k}\\
&=& cd^{n-1}\frac{1-\left(\frac{b}{d}\right)^{n}}{1-\left(\frac{b}{d}\right)}\\
&=& cd^{n-1}\frac{1-\frac{b^{n}}{d^{n}}}{1-\frac{b}{d}}\\
&=& cd^{n-1}\frac{\frac{d^{n}-b^{n}}{d^{n}}}{\frac{d-b}{d}}\\
&=& cd^{n-1}\frac{d^{n}-b^{n}}{d^{n}}\cdot\frac{d}{d-b}\\
&=& \frac{c\left(d^{n}-b^{n}\right)}{d-b}
\end{eqnarray}$$
 [/INST] Argh... use Wilf's techniques from "generatingfunctionology". Start defining:
$$
A(z) = \sum_{n \ge 0} a_n z^n
$$
Also write:
$$
a_{n + 1} = b a_n + c d^n
$$
Multiply by $z^n$, add over $n \ge 0$:
$$
\frac{A(z) - a_0}{z} = b A(z) + c \frac{1}{1 - d z}
$$
Solve for $A(z)$, express as partial fractions. The resulting terms are of the forms:
$$
(1 - \alpha z)^{-m}
  = \sum_{n \ge 0} \binom{-m}{n} (- \alpha)^n z^n
  = \sum_{n \ge 0} \binom{n + m - 1}{m - 1} \alpha^n z^n
$$
Note that:
$$
\binom{n + m - 1}{m - 1} 
  = \frac{(n + m - 1) (n + m - 2) \ldots (n + 1)}{(m - 1)!}
$$
This is a polynomial in $n$ of degree $m - 1$.
$$
$$
</s>