Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm given $$ a_n = \sum_{i=2}^{n-2} a_ia_{n-i} \quad (n\geq 3), a_0 = a_1=a_2 = 1 $$ and I need to find the functional equation for the generating function satisfying the above equality. I obtained the correct answer, but I don't understand why some of the steps are allowed.

$$ \begin{align} f(x) &= \sum_{n=0}^{\infty} a_nx^n\\ &=\sum_{n=0}^{\infty} \sum_{i=2}^{n-2} a_i a_{n-i} x^n\\ &=\sum_{n=0}^{\infty} \sum_{i=2}^{n-2}a_ix^i a_{n-i}x^{n-i}\\ &=\sum_{n=2}^{\infty} \sum_{i=2}^{n-2} a_ix^i a_{n-i}x^{n-i} \text{ (since it doesn't make sense for $n$ to start at $0$})\tag1\\ &=\sum_{n=2}^{\infty} \sum_{i=2}^{\infty} a_ix^i a_{n-i}x^{n-i} \text{ (since terms past $n-2$ don't exist)} \tag2\\ &=\sum_{n=2}^{\infty} \sum_{i=2}^{\infty} a_ix^i a_{n}x^{n} \text{ (not sure)} \tag3 \end{align} $$ Therefore, $$ f(x) -1-x-x^2 = (f(x) -1 -x)^2. $$ So the equations $(1),(2)$, and $(3)$, I'm not sure why those steps are allowed (or if they're even correct). Could someone please help?

share|improve this question
    
Check your definition of $a_n$, as $a_3 = \sum_{i=2}^1 a_i a_{3-i}$. –  Glen O Apr 10 '13 at 0:29
1  
Here is a related problem. –  Mhenni Benghorbal Apr 10 '13 at 0:37
add comment

1 Answer

For this problem, I would go in the other direction:

$\begin{align} f^2(x) &= (\sum_{n=0}^{\infty} a_n x^n) (\sum_{m=0}^{\infty} a_m x^m)\\ &= \sum_{n=0}^{\infty} \sum_{m=0}^{\infty}a_n x^n a_m x^m\\ &= \sum_{n=0}^{\infty} \sum_{m=0}^{\infty}a_n a_m x^{n+m}\\ &= \sum_{i=0}^{\infty} \sum_{j=0}^{i}a_j a_{i-j} x^{i}\\ &= \sum_{i=0}^{\infty} x^i \sum_{j=0}^{i}a_j a_{i-j} \\ &= a_0^2+ 2 a_0 a_1 x + \sum_{i=2}^{\infty} x^i \sum_{j=0}^{i}a_j a_{i-j} \\ &= a_0^2+ 2 a_0 a_1 x + \sum_{i=2}^{\infty} x^i (2a_0 a_i + 2 a_1 a_{i-1} +\sum_{j=2}^{i-2}a_j a_{i-j} )\\ &= a_0^2+ 2 a_0 a_1 x + \sum_{i=2}^{\infty} x^i (2a_0 a_i + 2 a_1 a_{i-1} +a_i )\\ &= a_0^2+ 2 a_0 a_1 x + (2 a_0+1)\sum_{i=2}^{\infty} x^i a_i + 2 a_1\sum_{i=2}^{\infty} x^i a_{i-1}\\ &= a_0^2+ 2 a_0 a_1 x + (2 a_0+1)\sum_{i=2}^{\infty} x^i a_i + 2 a_1 x\sum_{i=2}^{\infty} x^{i-1} a_{i-1}\\ &= a_0^2+ 2 a_0 a_1 x + (2 a_0+1)(f(x)-a_0-x a_1)+ 2 a_1 x\sum_{i=1}^{\infty} x^{i} a_{i}\\ &= a_0^2+ 2 a_0 a_1 x + (2 a_0+1)(f(x)-a_0-x a_1)+ 2 a_1 x (f(x)-a_0)\\ &= a_0^2+ 2 a_0 a_1 x + f(x)(2 a_1 x+2 a_0+1)-(2 a_0+1)(a_0x+ a_1)- 2 a_0 a_1 x\\ &= a_0^2 + f(x)(2 a_1 x+2 a_0+1)-(2 a_0+1)(a_0x+ a_1)\\ &= 1 + f(x)(2 x+3)-3(x+1)\\ &= f(x)(2 x+3)-3x-2\\ \end{align} $

This gives a quadratic equation for $f(x)$ (as expected, from the recursion for $a_n$):

$f^2 - (2x+3)f + 3x+2 = 0$.

Solving, the discriminant is $(2x+3)^2 - 4(3x+2) = 4x^2+12x+9-12x-8 =4x^2+1 $, so the solutions are $f(x) = \frac{2x+3 \pm \sqrt{4x^2+1}}{2} $. Since $f(0) = 1$, we have to take the minus sign, so $f(x) = \frac{2x+3 - \sqrt{4x^2+1}}{2} $.

There is a significant chance that there is some error here (since I did it off the top of my head), but the basic idea is that this type of recurrence always leads to a quadratic equation in the generating function.

Note that the coefficients of all the odd powers of $x$ (from $x^3$ on) are zero, which agrees with Glenn O's comment about $a_3$.

Also, I do not know whether or not it is a coincidence that the discriminant does not have an $x$ term - if it did, expanding the square root would be a lot harder.

share|improve this answer
    
your solution doesn't match the solution in the text :[ –  AlanH Apr 10 '13 at 18:33
    
As I said, I did it off the top of my head. Please tell me if you find the error(s) and I will make any needed corrections. –  marty cohen Apr 10 '13 at 22:10
    
yeah, it's not a big deal. :) I was just sort of stating it as an fyi. –  AlanH Apr 10 '13 at 22:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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