First of all, I want to make an apology for my English for I'm not an English native speaker.
I'm reading Discrete Mathematics and its Applications recent days, and I am stumped by these three problems.
- $a_k=a_{k-1}+2a_{k-2}+2^k, a_0=4, a_1=12$
- $a_k=4a_{k-1}-4a_{k-2}+k^2, a_0=2, a_1=5$
- $a_k=2a_{k-1}-3a_{k-2}+4^k+6, a_0=20, a_1=60$
Anyone has any idea? Your replies will be highly appreciated.
Problem solved. Thanks to you all. And here are my solutions.
Problem 1. $$\begin{cases}a_k=a_{k-1}+2a_{k-2}+2^k\\ a_0=4\\ a_1=12\end{cases}$$ Let $f(x)$ denote the generating function for the sequence $a_k$, then we get $f(x)=\sum\limits_{k\ge0}a_kx^k$
Take the first equation, then multiply each term by $x^k$
$$a_kx^k=a_{k-1}x^k+2a_{k-2}+2^kx^k$$
And sum each term from 2 since it's a 2-order recurrence relation.
$$\begin{align*}\sum\limits_{k\ge2}a_kx^k&=\sum\limits_{k\ge2}a_{k-1}x^k + \sum\limits_{k\ge2}2a_{k-2}x^k+\sum\limits_{k\ge2}2^kx^k\\&=\sum\limits_{k\ge2}a_{k-1}x^k + 2\sum\limits_{k\ge2}a_{k-2}x^k+\sum\limits_{k\ge2}2^kx^k\end{align*}$$
The idea is to manipulate each term so that you can write them as expressions in terms of the generating function $f(x)$ and known series representations.
$\begin{align*}\sum\limits_{k\ge2}a_kx^k&=\left(\sum\limits_{k\ge2}a_kx^k+a_1x+a_0\right)-a_1x-a_0\\&=\sum\limits_{k\ge0}a_kx^k-a_1x-a_0\\&=f(x)-4x-12\end{align*}$
$\begin{align*}\sum\limits_{k\ge2}a_{k-1}x^k&=x\sum\limits_{k\ge2}a_{k-1}x^{k-1}\\&=x\sum\limits_{k\ge1}a_kx^k\\&=x\left(\sum\limits_{k\ge0}a_kx^k-a_0\right)\\&=x(f(x)-4)\end{align*}$
$\begin{align*}\sum\limits_{k\ge2}a_{k-2}x^k&=x^2\sum\limits_{k\ge2}a_{k-2}x^{k-2}\\&=x\sum\limits_{k\ge0}a_kx^k\\&=x^2f(x)\end{align*}$
$\begin{align*}\sum\limits_{k\ge2}2^kx^k&=\sum\limits_{k\ge0}2^kx^k-2x-1\\&=\frac{1}{1-2x}-2x-1\end{align*}$
Right now, we have
$$f(x)-4x-12=x(f(x)-4)+2x^2f(x)+\frac{1}{1-2x}-2x-1$$
Rewrite the equation to solve $f(x)$, and we have
$$f(x)=\frac{2}{3}\frac{1}{(1-2x)^2}+\frac{38}{9}\frac{1}{1-2x}-\frac{8}{9}\frac{1}{1+x}$$
Finally, $$\begin{align*}a_k&=\frac{2}{3}C(2+k-1, 2-1)2^k+\frac{38}{9}·2^k-\frac{8}{9}(-1)^k\\&=\frac{2}{3}(1+k)2^k+\frac{38}{9}·2^k-\frac{8}{9}(-1)^k\\&=\frac{44}{9}·2^k+\frac{2}{3}k·\frac{k}{3}-\frac{8}{9}(-1)^k\end{align*}$$
Problem 2.
Most steps are the same as they were in problem 1, so I'll only write the steps of conjugating $\sum\limits_{k\ge2}k^2x^k$
$$\begin{align*}\sum\limits_{k\ge2}k^2x^k&=\sum\limits_{k\ge0}k^2x^k-x\\&=x\sum\limits_{k\ge0}k^2x^{k-1}-x\\&=x\sum\limits_{k\ge0}k·kx^{k-1}-x\\&=x\left(\sum\limits_{k\ge0}k·x^k\right)'-x\\&=x\left(x\sum\limits_{k\ge0}k·x^{k-1}\right)'-x\\&=x\left(x\left(\sum\limits_{k\ge0}x^k\right)'\right)'-x\\&=x\left(x\left(\frac{1}{1-x}\right)'\right)'-x\\&=x\left(\frac{x}{(1-x)^2}\right)'-x\\&=\frac{x(1+x)}{(1-x)^3}-x\end{align*}$$
My notes, using generating functions to solve recurrence relations
Here's a (partial) solution for the second recurrence relation. There's no particular reason for me having chosen this particular recurrence among the other two; this is just used as an example to give you an idea of how to solve the others. I intentionally left out most of the details to let this serve more as a reference for you to check your solution at different checkpoints rather than as an answer key. $$\begin{cases}a_k=4a_{k-1}-4a_{k-2}+k^2\\ a_0=2\\ a_1=5\end{cases}$$ Let $f(x)$ denote the generating function for the sequence $a_k$; that is, $f(x)=\sum\limits_{k\ge0}a_kx^k$. Taking the first equation, multiply each term by $x^k$ and sum each term over all positive $k\ge2$. (Why?) $$\color{red}{\sum_{k\ge2}a_kx^k}=4\color{blue}{\sum_{k\ge2}a_{k-1}x^k}-4\color{green}{\sum_{k\ge2}a_{k-2}x^k}+\color{orange}{\sum_{k\ge2}k^2x^k}$$ The idea is to manipulate each term so that you can write them as expressions in terms of the generating function $f(x)$ and known series representations. For instance, consider the LHS: $$\begin{align*}\sum_{k\ge2}a_kx^k&=\sum_{k\ge2}a_kx^k+a_1x+a_0-a_1x-a_0\\&=\sum_{k\ge0}a_kx^k-a_1x-a_0\\&=f(x)-5x-2\end{align*}$$ Doing the same throughout, you end up with a rewritten equation that can be solved for $f(x)$. $$\begin{align*}\color{red}{f(x)-5x-2}&=4\color{blue}{x(f(x)-2)}-4\color{green}{x^2f(x)}+\color{orange}{\frac{x(1+x)}{(1-x)^3}-x}\\[1ex] f(x)&=\frac{2}{(1-x)^3}+\frac{5}{(1-x)^2}+\frac{13}{1-x}+\frac{6}{(1-2x)^2}-\frac{24}{1-2x} \end{align*}$$ From here, you need to determine an appropriate series representation for $f(x)$. All the information you need happens to be contained in the geometric series, $$\sum_{k\ge0}x^k=\frac{1}{1-x}\quad\text{for }|x|<1$$ and its derivatives.
You should arrive at the final solution $$a_k=20-9(2^{1+k})+8k+3k(2^{1+k})+k^2$$