1
$\begingroup$

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.

  1. $a_k=a_{k-1}+2a_{k-2}+2^k, a_0=4, a_1=12$
  2. $a_k=4a_{k-1}-4a_{k-2}+k^2, a_0=2, a_1=5$
  3. $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

$\endgroup$

closed as off-topic by 6005, Claude Leibovici, user147263, Najib Idrissi, N. F. Taussig Oct 19 '15 at 10:04

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – 6005, Claude Leibovici, Najib Idrissi, N. F. Taussig
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ They are somewhat different from each other in detail, but all can be solved by finding the general solution of the homogeneous equation obtained by dropping the non-$a_i$ part, and a particular solution of the original inhomogeneous one. $\endgroup$ – André Nicolas Oct 16 '15 at 5:34
  • $\begingroup$ @AndréNicolas Oh, it works for me! But it seems that to find a particular solution still needs to solve the characteristic equation of the homogeneous equation, is this calculation a must? Or say is it possible that we don't need to find any particular solution but only use generating functions to solve any given recurrence relations? $\endgroup$ – 0xBBC Oct 16 '15 at 6:42
  • $\begingroup$ Generating functions and the methods I suggested are fairly close to each other, one can translate back and forth. It is mainly a matter of preference. After one has the generating function, there is still often a certain amount of work that needs to be done to get an explicit closed form, if there is one. $\endgroup$ – André Nicolas Oct 16 '15 at 6:48
  • $\begingroup$ @AndréNicolas I see. Thank you:) $\endgroup$ – 0xBBC Oct 16 '15 at 8:05
1
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ I spent a whole morning on writing the complete solutions of these three recurrence relations following your answer, and I managed to solve them all:) It took me almost 2 hrs to write down the whole solution for problem 2, 40 minutes for problem 1 and less than an half hour for problem 3. Nevertheless, it's a bit complex to use generating functions to solve recurrence relations, indeed. My thanks to you for your great help is beyond words. $\endgroup$ – 0xBBC Oct 17 '15 at 3:20
  • $\begingroup$ You're most welcome, I'm glad I could be of some help! $\endgroup$ – user170231 Oct 17 '15 at 12:37

Not the answer you're looking for? Browse other questions tagged or ask your own question.