Solving Recurrence Relations with generating functions when the variable is in the function.

Question

I'm studying for a midterm and couldn't figure out these three recurrences that I came across:

1. $i_{n+1}=2ni_n+2i_n+2$ with initial condition $i_0=1$
2. $j_{n+1}=3j_n+1$ with initial condition $j_1=1$
3. $k_n=k_{n-1}+n+6$ with initial condition $k_0=0$

Solutions:

1. $i_k=2^kk!+\frac{2^kk!}{1!}+\frac{2^{k-1}k!}{2!}+\ldots+\frac{2k!}{k!}$
2. $j_n=\frac{1}{2}(3^n-1)$
3. $k_n=\frac{n^2+13n}{2}$

The way we have been solving this is as follows: Suppose for example that $a_{k+1}=2a_k+4^k$ with initial condition $a_1=3$. Then from the recurrence we can derive $a_0=1$ even though $a_0$ is not defined. Now multiplying by $x^k$ and summing yields:

$$\sum^\infty_{k=0}a_{k+1}x^k=2\sum^\infty_{k=0}a_kx^k+\sum^\infty_{k=0}4^kx^k$$

Then from here we just solve the recurrence by factoring out an $x$, subtracting off initial values, and using partial fractions.

However, when I do that for $i_n$ and $k_n$ above, everything gets wonky with the $n$ terms... not sure how to resolve these. I tried using exponential generating functions (we never solve differential equations with these though... not that far), but it got nowhere. Also, with $j_n$ at the end I got $\frac{x}{1-3x}$ and I wasn't sure what to make of the extra $x$ term. But $j_n$ seems so simple that generating functions may be overkill? (Still, nothing too fancy though)

Any help would be greatly appreciated!

Answer 1

Using generating functions on the first one gets a bit messy; since it’s first order, you can simply ‘unwind’ the recurrence. In what follows I use the notation

$$x^{\underline k}=\underbrace{x(x-1)\ldots(x-k+1)}_{k\text{ factors}}$$

for the falling factorial power.

Shifting the index by $1$, we see that the recurrence can be written $i_n=2ni_{n-1}+2$. Now

$$\begin{align*} i_n&=2ni_{n-1}+2\\ &=2n\big(2(n-1)i_{n-2}+2\big)+2\\ &=2^2n(n-1)i_{n-2}+2^2n+2\\ &=2^2n(n-1)\big(2(n-2)i_{n-3}+2\big)+2^2n+2\\ &=2^3n(n-1)(n-2)i_{n-3}+2^3n(n-1)+2^2n+2\\ &\;\;\vdots\\ &=2^kn^{\underline k}i_{n-k}+\sum_{\ell=0}^{k-1}2^{\ell+1}n^{\underline\ell}\\ &\;\;\vdots\\ &=2^nn^{\underline n}i_0+\sum_{\ell=0}^{n-1}2^{\ell+1}n^{\underline\ell}\\ &=2^nn!+\sum_{\ell=0}^{n-1}\frac{2^{\ell+1}n!}{(n-\ell)!}\\ &=2^nn!+\sum_{\ell=1}^n\frac{2^{n+1-\ell}}{\ell!}\;, \end{align*}$$

which is exactly the solution that you have. The step in the middle with $i_{n-k}$ is recognition of the pattern that by that point is pretty clear, but it’s not actually rigorous. To justify the result now that we’ve found it, we really ought to prove it by induction; this is pretty straightforward, and I’ll leave it to you.

I agree that generating functions are overkill for the second problem. One simple approach is to let $x_n=j_n-d$ for some as yet undetermined constant $d$. Then $j_n=x_n+d$, so

$$x_n+d=3(x_{n-1}+d)+1=3x_{n-1}+3d+1\;,$$

and therefore $x_n=3x_{n-1}+2d+1$. If we now set $d=-\frac12$, we have $x_n=3x_{n-1}$, for which the closed form is obvious:

$$x_n=3^{n-1}x_1=3^{n-1}\left(j_1-\left(-\frac12\right)\right)=\frac{3^n}2\;.$$

Finally,

$$j_n=x_n-\frac12=\frac{3^n-1}2\;.$$

However, the solution using generating functions isn’t bad in this case. We have $j_n=3j_{n-1}+1$ valid for $n\ge 1$ on the assumption that $j_0=0$. If $g(x)$ is the generating function, we can multiply the recurrence by $x^n$ and sum over $n\ge 1$ to get

$$\begin{align*} g(x)&=\sum_{n\ge 1}j_nx^n\\ &=3\sum_{n\ge 1}j_{n-1}x^n+\sum_{n\ge 1}x^n\\ &=3x\sum_{n\ge 1}j_nx^n+\sum_{n\ge 1}x^n\\ &=3xg(x)+\frac{x}{1-x}\;, \end{align*}$$

and hence

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

so that

$$j_n=\frac12\left(3^n-1\right)$$

for $n\ge 1$.

Finally, I’d simply ‘unwind’ the third one:

$$\begin{align*} k_n&=k_{n-1}+n+6\\ &=k_{n-2}+(n-1)+n+2\cdot6\\ &=k_{n-3}+(n-2)+(n-1)+n+3\cdot6\\ &\;\;\vdots\\ &=k_{n-\ell}+\sum_{i=0}^{\ell-1}(n-i)+6\ell\\ &\;\;\vdots\\ &=k_0+\sum_{i=0}^{n-1}(n-i)+6n\\ &=\sum_{i=1}^ni+6n\\ &=\frac{n(n+1)}2+6n\\ &=\frac{n^2+13n}2\;. \end{align*}$$