Solving linear recurrence relation

Question

Solve the following linear recurrence relation:

$$h_n=4h_{n-1}-4h_{n-2}+n^2 2^n$$

for $n\geq2$ and $h_0=h_1=1$

Answer 1

HINT: First solve the homogeneous recurrence $h_n=4h_{n-1}-4h_{n-2}$. Then find a particular solution; slide $20$ of this PDF tells you what form of particular solution to look for and is followed by an example. Add the particular solution to the general solution of the homogeneous recurrence, and you’ll have the general solution of the non-homogeneous recurrence. Finally, use the initial values to pin down the arbitrary constants in the general solution.

Answer 2

Hint:

• $\frac{h_n}{2^n}=2\cdot \frac{h_{n-1}}{2^{n-1}}-\frac{h_{n-2}}{2^{n-2}}+n^2$

define $a_n:=\frac{h_n}{2^n}$, then $a_n=2\cdot a_{n-1}-a_{n-2}+n^2$

• $(a_n-a_{n-1})=(a_{n-1}-a_{n-2})+n^2$

define $b_n:=a_n-a_{n-1}(n\ge 1)$, then $b_n=b_{n-1}+n^2$

You will find the result once you know the sum $\sum_{k=1}^n k^2$

Answer 3

$$h_n - 2h_{n-1} = 2(h_{n-1} - 2h_{n-2}) + n^2 \cdot 2^n$$ Let $h_n - 2h_{n-1} = f_n$. We then have $$f_n = 2f_{n-1} + n^2 \cdot 2^n = 2(2f_{n-2} + (n-1)^2 \cdot 2^{n-1}) + n^2 \cdot 2^n = 4 f_{n-2} + 2^n \cdot (n^2 + (n-1)^2)$$ Hence, by induction, we have $$f_n = 2^n \cdot (n^2 + (n-1)^2 + \cdots + 2^2 + 1^2) + 2^n \cdot f_0 = 2^n \cdot \left( f_0 + \dfrac{n(n+1)(2n+1)}6\right)$$ Hence, \begin{align} h_n & = 2h_{n-1} + 2^n \cdot \left( c + \dfrac{n(n+1)(2n+1)}6\right)\\ & = 4h_{n-2} + 2^n \cdot \left(2c + \dfrac{n(n+1)(2n+1) + (n-1)n(2n-1)}6\right)\\ & = 2^n \cdot h_{0} + 2^n \cdot \left(nc + \dfrac{\displaystyle \sum_{k=1}^n k(k+1)(2k+1)}6\right) \end{align} Hence, $$h_n = 2^n \left(an^4+bn^3+cn^2+dn+e\right)$$ where the $a,b,c,d$ and $e$ can be obtained using the recurrence in terms of the initial values $h_0$ and $h_1$.

Answer 4

Use generating functions. Define $H(z) = \sum_{n \ge 0} h_n z^n$, and write the recurrence as:

$$ h_{n + 2} = 4 h_{n + 1} - 4 h_n + 4 (n + 2)^2 2^n $$ By the properties of ordinary generating functions (see e.g. Wilf's "generatingfunctionology") with the operator $z D = z \dfrac{d}{d z}$ : $$ \begin{align*} \frac{H(z) - 1 - z}{z^2} &= 4 \frac{H(z) - 1}{z} - 4 H(z) + 4 (z D + 2)^2 \frac{1}{1 - 2 z} \\ H(z) &= \frac{2}{(1 - 2 z)^5} - \frac{3}{(1 - 2 z)^4} - \frac{3}{(1 - 2 z)^3} + \frac{21}{2 (1 - 2 z)^2} - \frac{19}{2 (1 - 2 z)} + 4 \end{align*} $$ Using $\binom{-r}{s} = (-1)^r \binom{r + s - 1}{r - 1}$ the powers give polynomials in $n$ multiplying $2^n$, a computer algebra system like maxima reduces this mess to a simpler expression.