Question

Solve the recurrence relation hn=3hn-1 -4n using generating function

Answer 1

Let

$H(x)=\displaystyle\sum_{n\ge0}h_nx^n$

be the generating function for the sequence $h_n$. Then

$h_n=3h_{n-1}-4n$
$\displaystyle\sum_{n\ge1}h_nx^n=3\sum_{n\ge1}h_{n-1}x^n-4\sum_{n\ge1}nx^n$
$\displaystyle\sum_{n\ge0}h_nx^n-h_0=3x\sum_{n\ge0}h_nx^n-4x\sum_{n\ge0}nx^{n-1}$
$\displaystyle H(x)-h_0=3xH(x)-4x\frac{\mathrm d}{\mathrm dx}\sum_{n\ge0}x^n$
$(1-3x)H(x)=h_0-4x\dfrac{\mathrm d}{\mathrm dx}\left[\dfrac1{1-x}\right]$
$(1-3x)H(x)=h_0-\dfrac{4x}{(1-x)^2}$
$H(x)=\dfrac{h_0}{1-3x}-\dfrac{4x}{(1-3x)(1-x)^2}$

Decompose the latter term into partial fractions:


$-\dfrac{4x}{(1-3x)(1-x)^2}=\dfrac2{(1-x)^2}+\dfrac1{1-x}-\dfrac3{1-3x}$

so that

$H(x)=\dfrac{h_0-3}{1-3x}+\dfrac1{1-x}+\dfrac2{(1-x)^2}$
$\implies H(x)=\displaystyle\sum_{n\ge0}(h_0-3)3^nx^n+\sum_{n\ge0}x^n+\sum_{n\ge0}2nx^n$
$\implies H(x)=\displaystyle\sum_{n\ge0}\bigg((h_0-3)3^n+2n+1\bigg)x^n$
$\implies h_n=(h_0-3)3^n+2n+1$