Find a closed form of the sequence $a_n$ that satisfies $a_{n+1}=bc^n+da_n$ related to Galton-Watson tree. Find a closed form of the sequence $a_n$ that satisfies
$$a_{n+1}=bc^n+da_n$$
where $a_0=0;\ b,c,d>0;\ c\neq1$.
The background is that I get this iterative equation when computing the variance of
$$Z_n:= \text{the number of $n$-th generation nodes on a Galton-Watson tree}$$
Suppose in this Galton-Watson tree, each node produces offsprings according to an integer-valued nonnegative r.v. $N$, and $E[N]=m,\ {\rm var}(N)=\sigma^2$. After some work I obtained
$${\rm var}(Z_{n+1})=\sigma^2m^n+m^2{\rm var}(Z_n)$$
but I don't know how to continue to solve ${\rm var}(Z_n)$.
 A: You have
$$a_{n+1} = bc^n + da_n \implies ca_{n+1} = bc^{n+1} + cda_n \tag{1}\label{eq1A}$$
and also
$$a_{n+2} = bc^{n+1} + da_{n+1} \tag{2}\label{eq2A}$$
Next, \eqref{eq2A} minus \eqref{eq1A} gives
$$\begin{equation}\begin{aligned}
a_{n+2} - ca_{n+1} & = da_{n+1} - cda_{n} \\
a_{n+2} & = (c + d)a_{n+1} - cda_{n}
\end{aligned}\end{equation}\tag{3}\label{eq3A}$$
This is now a homogenous linear difference equation. The characteristic equation is
$$\begin{equation}\begin{aligned}
\lambda^2 & = (c + d)\lambda - cd \\
\lambda^2 - (c + d)\lambda + cd & = 0 \\
(\lambda - c)(\lambda - d) & = 0
\end{aligned}\end{equation}\tag{4}\label{eq4A}$$
Assuming $c \neq d$, the general solution is
$$a_n = e_1(c^n) + e_2(d^n) \tag{5}\label{eq5A}$$
You have $a_0 = 0$, plus \eqref{eq1A} gives $a_1 = b$. Thus, you have
$$0 = e_1 + e_2 \tag{6}\label{eq6A}$$
$$b = e_1c + e_2d \tag{7}\label{eq7A}$$
From \eqref{eq6A}, you have $e_2 = -e_1$, which substituted into \eqref{eq7A} gives
$$b = e_1c - e_1d \implies e_1 = \frac{b}{c - d} \tag{8}\label{eq8A}$$
As such, the final result is
$$a_n = \frac{b\left(c^n - d^n\right)}{c-d} \tag{9}\label{eq9A}$$
If applicable in your situation, I'll leave it to you to solve for the case where $c = d$, e.g., as shown in the Solution with duplicate characteristic roots section.
