Solving a recurrence relation $a_n =\sum_{i=0}^{n-2} a_i $

Question

I'm given the following recursive formula:

$a_n =\sum_{i=0}^{n-2} a_i \\a_1 = 1 , \; a_0 = 1 $

I noticed that $\;a_2 = 1$ as well , and for any $n>3 : \, a_n - a_{n-1} =\sum_{i=0}^{n-2} a_i \; - \sum_{i=0}^{n-3} a_i = a_{n-2} $

so this seems close to Fibonacci numbers for any $n\;\;$ that's greater than 3. however , when I attempt substituting $a_n \; $ for $\; x^n$ , I get the familiar solutions :

$ \; x_1 = \frac{1+\sqrt5}{2} \; x_2 = \frac{1-\sqrt5}{2}\\$

so I'm looking for a solution of the form $a_n = c_1(\frac{1+\sqrt5}{2})^n+c_2(\frac{1-\sqrt5}{2})^n$

and applying boundary values I get : $c_1+c_2 = 1 \\ c_1-c_2 = \frac{1}{\sqrt5}\\ c_2-c_1 = \frac{1}{\sqrt5}$

which is obviously wrong, needless to say the Fibonacci formula doesn't work for $n>3 $. Could anyone tell me what is wrong with my solution? and maybe propose a different solution/ approach / hint?

thanks ahead.

Answer 1

Hint:

$$a_n = \sum_{i=0}^{n-2} a_i = a_{n-2} + \sum_{i=0}^{n-3}a_i = a_{n-2} + a_{n-1}$$

which means that yes, you should be getting something very similar to the Fibonacci formula. However, the equation

$$a_n=a_{n-2} + a_{n-1}$$ is only true for $n\geq 3$ and is not true for $n=2$.

Answer 2

This is just one simple example of a general situation. It's easy to check that for your sequence $\ a_n = F_n\ $ if $\ n>0,\ $ but that $\ a_0 = 1 \ne F_0.\ $ Thus, your sequence is the same as the Fibonacci sequence except at $\ n=0.$ It is easy to give other examples of sequences that are the same as well known sequences except for one or more values of $\ n.\ $ For example, the OEIS sequence A011782 "Expansion of (1-x)/(1-2*x) in powers of x". This sequence is the same as the powers of $2$ except for the extra first term. The formula for this sequence is $\ a_0 = 1,\ a_n = 2^{n-1}\ $ and a recursion for it is $\ a_n = \sum_{i=0}^{n-1} a_i. \ $ This recursion is very similar to your recursion. Notice that your proposed formula $\ a_n=c_1\big(\frac{1+\sqrt5}{2}\big)^n+c_2\big(\frac{1-\sqrt5}{2}\big)^n \ $ is only valid for $\ n>0\ $ therefore $\ c_1+c_2=1\ $ is not true. Using $\ a_1\!=\!a_2\!=\!1,\ $ you can get that $\ c_1\!=\!-c_2\!=\!1/\sqrt{5}.$