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 self-studying generating functions (using GeneratingFunctionology as a text). I came across this programming problem, which I immediately recognized as a modification of the Fibonacci sequence. I wanted to place my newly found generating function techniques to work, so I tried to solve the recurrence.

The problem basically boils down to solving:

$$a_{n+2} = a_{n+1} + ka_n$$ Where $n \ge 0$, and $k$ is some positive integer. And, $a_0 = 1$, $a_1 = 1$.

However, my solution (below, but not really simplified, since I'm just plugging it into a computer) yields values that too great by a factor of $k$.

My solution:

$$a_n = \frac{r_2^{n+1} - r_1^{n+1}}{(r_2-r_1)r_1^{n+1}r_2^{n+1}}$$ Where: $$r_1 = \frac{-1 - \sqrt{1+4k}}{2k}$$ $$r_2 = \frac{-1 + \sqrt{1+4k}}{2k}$$

If someone could help me understand where I went wrong, I'd much appreciate it. (I don't see why I'm too great by a factor of $k$.)

My work is as below:

$$a_{n+2} = a_{n+1} + ka_n$$ $$\sum_{n\ge0}a_{n+2}x^n = \sum_{n\ge0}a_{n+1}x^n + k\sum_{n\ge0}a_{n}x^n$$

Let $A(x) = \sum_{n\ge0}a_nx^n$. Then:

$$\frac{A(x) - a_0 - xa_1}{x^2} = \frac{A(x) - a_0}{x} + kA(x)$$ $$A(x)\left(\frac{1}{x^2} -\frac{1}{x} - k\right) = \frac{1+x}{x^2} - \frac{1}{x}$$ $$A(x)\left(\frac{1 - x - kx^2}{x^2}\right) = \frac{1}{x^2}$$ $$A(x)= \frac{1}{1 - x - kx^2}$$

Now, factoring the denominator yields two roots, $r_1$ and $r_2$ as denoted above. This, in turn, yields: $$A(x) = \frac{1}{(x-r_1)(x-r_2)}$$ Partial fractions: $$A(x) = \frac{1}{r_2-r_1}\frac{1}{(r_1 - x)} - \frac{1}{r_2-r_1}\frac{1}{(r_2 - x)}$$ $$A(x) = \frac{1}{(r_2-r_1)(r_1)}\frac{1}{(1 - \frac{x}{r_1})} - \frac{1}{(r_2-r_1)(r_2)}\frac{1}{(1 - \frac{x}{r_2})}$$ $$A(x) = \frac{1}{(r_2-r_1)(r_1)}\sum_{n\ge0}{\left(\frac{x}{r_1}\right)^n} - \frac{1}{(r_2-r_1)(r_2)}\sum_{n\ge0}{\left(\frac{x}{r_2}\right)^n}$$

Combining: $$A(x) = \sum_{n\ge0} x^n \left(\frac{1}{(r_2-r_1)(r_1^{n+1})} - \frac{1}{(r_2-r_1)(r_2^{n+1})}\right)$$ Therefore: $$a_n = \frac{r_2^{n+1} - r_1^{n+1}}{(r_2-r_1)r_1^{n+1}r_2^{n+1}}$$

share|improve this question

2 Answers 2

up vote 4 down vote accepted

Something went wrong between

$$A(x)= \frac{1}{1 - x - kx^2}$$

And

$$A(x) = \frac{1}{(x-r_1)(x-r_2)}$$

share|improve this answer
    
Ummm... could you be more explicit? I just double-checked my quadratic formula, and it yields the roots in my answer... –  anorton Mar 14 '13 at 13:54
    
If you develop the denominator of the second equation, you won't get a $k \ x^2$ but a $x^2$ alone. Thus the factor $k$ (actually $-k$). Common mistake, to compute the roots correctly, but forget the leading coefficient in factorization. ;-) –  Jean-Claude Arbaut Mar 14 '13 at 13:56
    
Doh! Thanks. :) –  anorton Mar 14 '13 at 13:57

$$1-x-kx^2=-kx^2-x+1\Rightarrow x_{1,2}=\frac{1\pm\sqrt{1+4k}}{2}$$so

$$1-x-kx^2=-kx^2-x+1=(-k)(x-x_1)(x-x_2)=(-k)(x-\frac{1-\sqrt{1+4k}}{2})(x-\frac{1+\sqrt{1+4k}}{2})$$

share|improve this answer
    
Almost right :-) Were has gone $k$ ? –  Jean-Claude Arbaut Mar 14 '13 at 14:08
    
which k you mean –  Adi Dani Mar 14 '13 at 14:19
    
The one before $x^2$... –  Jean-Claude Arbaut Mar 14 '13 at 14:21
    
yes I see now is my mistake, thank you –  Adi Dani Mar 14 '13 at 14:27

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.