Proof for the given identity of $\frac{1}{1-az-bz^2}$

Question

I know that for $a,b\in \mathbb{R}$ we have the formula

$\frac{1}{1-az-bz^2}=\sum_{n=0}^{\infty}\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n-k}{k}a^{n-2k}b^{k}z^n$

However, I am unsure how to derive it. I'm sure that there exists some identity with regards to deriving the given formula, I just can't seem to find it.

I know that using the Taylor series we could write the expression $\frac{1}{1-az-bz^2}$ for example as

$\frac{1}{1-az-bz^2}=\sum_{n=0}^{\infty}\frac{a^n\Big(\frac{z}{1-bz^2}\Big)^{n+1}}{z}$ when $|b-1|<\Big| \frac{-1+az+z^2}{z^2}\Big|$

but I am unable to proceed from this point and this is all I could think of.

Answer 1

Here we use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series $A(z)$. We can write \begin{align*} A(z)&=\frac{1}{1-az-bz^2}=\sum_{n=0}^\infty \color{blue}{\alpha_n} z^n\\ &=\sum_{n=0}^\infty\left(\color{blue}{[t^n]A(t)}\right)z^n\tag{1} \end{align*} Note (1) is the wanted expansion in $z$ and we have to determine the coefficient $[t^n]A(t)$.

We obtain \begin{align*} \color{blue}{[t^n]}\color{blue}{A(t)}&=[t^n]\frac{1}{1-t(a+bt)}\\ &=[t^n]\sum_{k=0}^\infty t^k(a+bt)^k\tag{2.1}\\ &=\sum_{k=0}^n[t^{n-k}](a+bt)^k\tag{2.2}\\ &=\sum_{k=0}^n[t^k](a+bt)^{n-k}\tag{2.3}\\ &=\sum_{k=0}^n[t^k]\sum_{l=0}^{n-k}\binom{n-k}{l}(bt)^la^{n-k-l}\tag{2.4}\\ &\,\,\color{blue}{=\sum_{k=0}^n\binom{n-k}{k}b^ka^{n-2k}}\tag{2.5} \end{align*} and the claim follows.

Comment:

• In (2.1) we use the geometric series expansion.

• In (2.2) we apply the rule $[t^{p-q}]A(t)=[t^p]t^qA(t)$. We also set the upper limit of the sum to $n$. Other indices do not contribute since powers of $t$ are non-negative.

• in (2.3) we change the order of summation: $k\to n-k$.

• In (2.4) we apply the binomial theorem.

• In (2.5) we select the coefficient of $t^k$.

We could also set the upper limit of the sum in (2.5) to $\left\lfloor\frac{n}{2}\right\rfloor$, since $\binom{n-k}{k}=0$ if $\left\lfloor\frac{n}{2}\right\rfloor<k\leq n$.