# Recurrences for even and odd indexed of Fibonacci Numbers

I have a Recurrence: $$a_{0}=1$$ $$a_{n}=\sum_{k=0}^{n-1}(n-k)a_{k}$$ I have evaluated some a's:$a_{0}=1, a_{1}=1,a_{2}=3,a_{3}=8,a_{4}=21,a_{5}=55,...$. In the previous exercise on had to derive a generating Function for the even indexted Fibonacci Numbers. So these are definitely $F_{0}=1,F_{1}=1,F_{2}=3,F_{3}=8,F_{4}=21,...$

Then I had a detailed look on the summation: $$a_{0}=1$$ $$a_{1}=(1-0)*1=1$$ $$a_{2}=(2-0)*a_{0}+(2-1)*a_{1}=2*1+1*1=3$$ $$a_{3}=(3-0)*a_{0}+(3-1)*a_{1}+(3-2)*a_{2}=3*1+2*1+1*3=8$$ $$a_{4}=(4-0)*a_{0}+(4-1)*a_{1}+(4-2)*a_{2}+(4-3)*a_{3}=4*1+3*1+2*3+1*8=21$$

Its obviously linked to: Summation of Fibonacci numbers $F_n$ with $n$ odd vs. even

But i dont see how to proceed.

• Shouldn't it then be $a_0=0$? – lhf Jun 3 '18 at 11:46
• its 1, i think it uses $F_0=1, and F_1=1$, might be a typo, but its says $a_0 =1$ – thetha Jun 3 '18 at 11:47

## 1 Answer

The right-hand side is the convolution of sequences $\{n\}$ and $\{a_n\}$ (the term $0a_n$ is simply omitted). Taking the ordinary generating functions of both sides, we get $$A(x)-1=\frac{x}{(1-x)^2}A(x),$$ so that $$A(x)=\frac{(1-x)^2}{1-3x+x^2}=1+\frac{x}{1-3x+x^2},$$ and thus $$a_n=F_{2n}, \quad n\ge 1,$$ where the sequence $\{F_n\}$ starts with $F_0=0$, $F_1=1$.

• I dont untderstand the -1? the right side has an index shift with +1 right? – thetha Jun 3 '18 at 16:05
• @thetha No, there is no shift since $(n-k)+k=n$, not $n-1$. There is simply a missing summand of $0a_n$ on the right that extends the sum to $k=n$. Since it doesn’t contribute anything, nothing is subtracted on the right in the functional equation. The $-1$ on the left is there because the convolution on the right has $0$th term equal to $0$ whereas $a_0=1$. – Alexander Burstein Jun 3 '18 at 16:09
• Okey i think i dont get you solution. I know I have a sequence (1,2,3,4,5,6....) the generating Function for this one is $\sum_{n \ge 0}(n+1) z^n=\frac{1}{(1-z)^2}$ When i multiplay this with x its a shift of the inder one to the right. Then i get $\frac{x}{(1-x)^2}$ – thetha Jun 3 '18 at 16:20
• @thetha That’s equivalent to what I did. – Alexander Burstein Jun 3 '18 at 16:34
• Thank you for the Explantation – thetha Jun 3 '18 at 16:35