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(\mathrm d)/(\mathrm dx)\sum_(n\ge0)x^n`

`(1-3x)H(x)=h_0-4x(\mathrm d)/(\mathrm dx)\left[\frac1{1-x}\right]`

`(1-3x)H(x)=h_0-(4x)/((1-x)^2)`

`H(x)=(h_0)/(1-3x)-(4x)/((1-3x)(1-x)^2)`

Decompose the latter term into partial fractions:



`-(4x)/((1-3x)(1-x)^2)=\frac2{(1-x)^2}+\frac1{1-x}-\frac3{1-3x}`

so that


`H(x)=(h_0-3)/(1-3x)+\frac1{1-x}+\frac2{(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`