2
$\begingroup$

I am a software engineer teaching myself combinatorics. This problem is destroying me, but I am following what I thought was the appropriate strategy to solve a recurrence. I am also confused as to how to refactor the recursion into a power series.

Problem

Let $G(x) = \sum_0^\infty a_kx^k$ be a generating function. Let $a_0 = 1$ and $a_1 = 0$ and $a_n = 6a_{n-1} + a_{n-2}$ for $n > 1$.

  • Show $G(x) = \frac{1-x}{1-x-6x^2}$.
  • Find real numbers A and B such that$G(x) = \frac{A}{1-ax} + \frac{B}{1-bx}$ where $(1-ax)(1-bx) = 1 - x - 6x^2$
  • Use geometric progression formula to expand $G(x)$ into a power series. Collect terms with $x^n$. The coefficient at $x^n$ will give you formula for $a_n$.

Attempt

  1. Show $G(x) = \frac{1-x}{1-x-6x^2}$.

    Using recurrence, it can be clearly seen that we can argue as follows: $G(x) = \sum_0^\infty a_kx^k = \sum_1^\infty6a_{k-1}x^k + \sum_2^\infty a_{k-2}x^k$. Note the sum starts at 1 and 2 on right side because it is not defined for values below this. Thus, we obtain the following expression on the right side by simplifying: $6x + x^2 + \frac{6x^3}{1-x} + \frac{x^4}{1-x}$ because $\sum_m^\infty ax^k = \frac{ax^m}{1-x}$. Clearly, this is wrong. I suspect that I did not set up the recurrence correctly?

  2. Find the real numbers A and B.

    I'm really frustrated by this. I get $A + B = 1$ and $Ab + Ba = 1$, but must I find what $a$ and $b$ are first? Otherwise I don't know how it is solvable? Unless in terms of $a$ and $b$ such as $B = \frac{ab+b}{-ab + bb}$ ?

  3. Problem expressed as power series. $1 + 1x^2 + 6x^3 + 37x^4 + ...$ Right?

I appreciate your patience while I work through these. I feel stupid, but I don't care. This is how you learn in self study and I would appreciate someone setting me straight on the above. I definitely know 1 is wrong, but not clear on where I went wrong. I think I have the right idea for 2. I'm not quite sure what is being asked for in 3.

$\endgroup$
  • $\begingroup$ Please check the recurrence and initial conditions: as they stand, they’re not consistent with $G(x)$ as given. $\endgroup$ – Brian M. Scott Dec 8 '15 at 23:12
  • $\begingroup$ Well, well, look who we have here : ) Nice to see that you're still at it. As for task 3, here's a hint: If you solve 1 you will have obtained the generating function for $(a_n)$ satisfying the recurrence. To extract that sequence, one method is to use partial fractions to split the generating function into a sum of geometric series. This you do in 2. Once that's done, you will have $G(z)=A/(1-ax)+B/(1-bx)$ for some $A,a,B,b$. The $n^{th}$ coefficient of $G(z)$, i.e. $a_n$, is then $Aa^n+Bb^n$ (since $A/(1-ax)=A\sum_{n=0}^\infty (ax)^n=\sum_{n=0}^\infty Aa^nx^n$ and same for $B/(1-bx)$). $\endgroup$ – A.Sh Dec 8 '15 at 23:42
2
$\begingroup$

I think you mistyped the recurrence; it should probably be $a_n = a_{n-1} + 6a_{n-2}$. Either that or the answer in (1) is wrong (although your answer to (3) corresponds to the recurrence you gave). In any case, to compute the generating function you have to be more careful with the indices. As you correctly point out, the sums on the right start with $i=1$ and $i=2$; you should write \begin{align*} G(x) &= \sum_0^\infty a_kx^k = a_0 + a_1x + \sum_2^{\infty} a_kx^k \\ &= a_0 + a_1x + \sum_2^\infty a_{k-1}x^k + \sum_2^\infty 6a_{k-2}x^k \\ &= 1 + \sum_1^\infty a_kx^{k+1} + \sum_0^\infty 6a_kx^{k+2} \\ &= 1 + x\sum_1^\infty a_kx^k + 6x^2\sum_0^\infty a_kx^k \\ &= 1 + x\sum_0^\infty a_kx^k - x + 6x^2\sum_0^\infty a_kx^k \\ &= 1-x + xG(x) + 6x^2G(x). \end{align*} Solving for $G(x)$ gives $$G(x) = \frac{1-x}{1-x-6x^2}.$$

  1. First factor $1-x-6x^2 = (1-3x)(1+2x)$, then use partial fractions.
$\endgroup$
1
$\begingroup$

You cant change the index by will, this is the fail. Every index must be from $k=0$, then you adjust it to get something identical to $G(x)$.

You apply the operator $\sum_{n\ge2}x^n$ to both sides of the equation:

$$\sum_{n\ge2}(a_n)x^n=\sum_{n\ge2}(6a_{n-1}+a_{n-2})x^n=\\ =G(x)-a_1x-a_0=6\sum_{n\ge2}a_{n-1}x^n+\sum_{n\ge2}a_{n-2}x^n=\\ =6x\sum_{n\ge2}a_{n-1}x^{n-1}+x^2\sum_{n\ge2}a_{n-2}x^{n-2}=\\ =6x\sum_{n\ge1}a_{n}x^{n}+x^2\sum_{n\ge0}a_{n}x^{n}=\\ =6x(-a_0+\sum_{n\ge0}a_{n}x^{n})+x^2\sum_{n\ge0}a_{n}x^{n}$$

Then we have $a_0=1$ and $a_1=0$ so

$$G(x)-1=6x(-1+G(x))+x^2G(x)\to\\ G(x)-6xG(x)-x^2G(x)=-6x+1\to \\ G(x)=\frac{6x-1}{x^2+6x-1}$$

Something seems wrong on the original post.

$\endgroup$
  • $\begingroup$ It would be a typo in the problem of the text I am reading. I agree. I am getting the same thing as you know that I fixed my indices. $\endgroup$ – hlyates Dec 9 '15 at 2:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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