How to solve recurrence relation $a_k = ba_{k−1} + cr^k$, assuming $b \neq r$ Solve for $a_k$ in terms of $a_0$ and the other parameters in the following recurrence relation:
$a_k = ba_{k−1} + cr^k$, assuming $b \neq r$.
 A: $\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\on}[1]{\operatorname{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

*

*With $\ds{b \not= r,\quad a_{k} = ba_{k − 1} + cr^{k}}$.

*\begin{align}
\mbox{Lets}\quad d_{k} & \equiv {a_{k} \over r^{k}} \implies d_{k} =
{b \over r}\,d_{k - 1} + c 
\\[2mm] \implies
d_{k} - {rc \over r - b}& =
{b \over r}\pars{d_{k - 1} - {rc \over r - b}}
\end{align}

\begin{align}
\implies &
d_{k} - {rc \over r - b} = \pars{b \over r}^{2}\pars{d_{k - 2} - {rc \over r - b}}
\\[2mm] & = \cdots =
\pars{b \over r}^{k}\pars{d_{0} - {rc \over r - b}}
\\[5mm] \implies &
d_{k} = {rc \over r - b} +
\pars{b \over r}^{k}\pars{d_{0} - {rc \over r - b}}
\\[5mm] \implies &
\bbx{a_{k} = {c \over r - b}\,r^{k + 1}\ +\
\pars{a_{0} - {rc \over r - b}}b^{k}} \\ &
\end{align}
A: Welcome!!
Generating function is the answer. Take $f(x)=\sum a_kx^k$, multiply by $x^k$ each sides and sum over $k$..
$$
\sum a_kx^k=bx\sum a_{k-1}x^{k-1}+c\sum r^kx^k
$$
led to
$$
f(x)=bxf(x)+\frac{c}{1-rx}
$$
or
$$
f(x)=\frac{c}{(1-bx)(1-rx)}.
$$
Expand by partial fraction and you can find your $a_k$, or you can use the fact that
$$
f(x)=c\sum b^kx^k\sum r^kx^k
$$
can be written as
$$
f(x)=c\sum_{n\geq0}\sum_{0\leq k\leq n}b^kr^{n-k}x^k
$$
and so
$$
f(x)=\sum_nc\frac{b^{n+1}-r^{n+1}}{b-r}x^n.
$$
A: Hint:
$$a_k = ba_{k−1} + cr^k\\
a_{k+1} = ba_k+cr^{k+1}\\
\implies a_{k+1}-ba_k=r(a_k-ba_{k-1})\\
\implies a_{k+1}-ra_k=b(a_k-ra_{k-1})
$$
So both $a_{k+1}-ba_k$ and $a_{k+1}-ra_k$ are geometric sequences. Can you start from here?
If you still get stuck, take a look at this post.
