discrete math>Recurrence relation>how find the general function of $a(n)=2a(n-1)+n^2$

Question

this is a question from discrete math exam i had

$$a(n)=\sum_{k=0}^nk^22^{n-k}$$

i need to find a general function of this (without the summation and $k$)

it looks like $a(n)=2a(n-1)+n^2$, $a(1)=1$, and $a(2)=6$.

(if there is no mistakes in my calculations)

now the question is how to solve this non-homogeneous recurrence relation
(also it would be very nice know where i can read about solving non-homogeneous recurrence relations )

i think there is also a combinatorial proof to this .(but not for sure)

thanks in advance

Answer 1

Your recurrence is correct. It’s first-order, so you really need only one initial value, and you might as well use $a(0)=0$. One way to solve it is with generating functions. Multiply the recurrence by $x^n$ and sum over $n\ge 0$:

$$\begin{align*} \sum_{n\ge 0}a_nx^n&=\sum_{n\ge 0}\left(2a_{n-1}+n^2\right)x^n\\ &=\sum_{n\ge 0}2a_{n-1}x^n+\sum_{n\ge 0}n^2x^n\\ &=2x\sum_{n\ge 0}a_{n-1}x^{n-1}+\sum_{n\ge 0}n^2x^n\\ &=2x\sum_{n\ge 0}a_nx^n+\sum_{n\ge 0}n^2x^n\;, \end{align*}$$

where $a_{-1}=0$; note that the recurrence is then valid at $n=0$. If $g(x)=\sum_{n\ge 0}a_nx^n$, we now have

$$g(x)=2xg(x)+\sum_{n\ge 0}n^2x^n\;.$$

To find a closed form for $\sum_{n\ge 0}n^2x^n$, start with $\sum_{n\ge 0}x^n=\frac1{1-x}$. Differentiate both sides with respect to $x$, multiply both sides by $x$, differentiate again, and multiply again by $x$, and you’ll find (if I’ve made no mistakes) that

$$\sum_{n\ge 0}n^2x^n=\frac{x(1+x)}{(1-x)^3}\;.$$

Thus,

$$g(x)=\frac{x(1+x)}{(1-x)^3(1-2x)}\;.$$

If you now decompose the righthand side into partial fractions, you’ll find that each has a straightforward series expansion; for example,

$$\frac{a}{(1-x)^2}=a\sum_{n\ge 0}(n+1)x^n\;.$$

You can combine these expansions into a single power series and equate coefficients to get a closed form for $a_n$. I’ll leave the details to you, but I get $$a_n=6\cdot2^n-n^2-4n-6\;.$$

Answer 2

the question is how to solve this non-homogeneous recurrence relation

Consider the recursion $a(n)=ca(n-1)+b(n)$ and remember how one solves differential equations: first the homogeneous part, then the full equation. Here, the homogenous part is $a(n)=ca(n-1)$, solved by $a(n)=c^na(0)$ hence one looks for a sequence $(\alpha(n))$ such that $a(n)=c^n\alpha(n)$ solves the original recursion.

This yields $\alpha(n)=\alpha(n-1)+\beta(n)$, where $\beta(n)=c^{-n}b(n)$... And I guess you can take it from here?