2

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.

giorgioh
  • 322
  • You'll have to clarify what you mean by "substituting $a_n$ for $x^n$" as there are no $x$'s earlier in your question. In any case, these are the Fibonacci numbers, just with a different value of $a_0$. You can easily check you have $a_0=a_1=a_2=1$, $a_3=2$, $a_4=3$, $a_5=5$, etc. (and the pattern continues since you found $a_n=a_{n-1}+a_{n-2}$ for $n \geq 3$). – kccu Apr 25 '19 at 13:19
  • @kccu I actually meant solving the following : $ x^n = x^{n-1} + x^{n-2}$ which gives me the same solutions as the ones for the Fibonacci numbers, but was is then the closed formula in this case ? – giorgioh Apr 25 '19 at 13:22
  • 1
    You should not use $n=0$ as a boundary condition because your sequence does not satisfy $a_2=a_0+a_1$. – kccu Apr 25 '19 at 13:25
  • You will not be able to write $a_n = c_1 \varphi^n + c_2 \psi ^n$ for all $n$, because for $n \geq 1$ the only solution will be the same $c_1$ and $c_2$ that give you the Fibonacci numbers, yet your sequence differs from the Fibonacci numbers at the $0$th term. – kccu Apr 25 '19 at 13:28
  • @5xum $a_2 = \sum_{n=0}^{2-2}a_i = \sum_{n=0}^0 a_i = a_0 = 1$. And $a_0+a_1=1+1=2 \neq 1 = a_2$. – kccu Apr 25 '19 at 13:30
  • @5xum manually calculating for $a_2 $ using the recurrence relation I get $a_2 = a_0 = 1 \ne 2 = a_0+a_1$ – giorgioh Apr 25 '19 at 13:31
  • @kccu Thank you very much I'll consider what you said , I think that helped me get the correct solution. – giorgioh Apr 25 '19 at 13:32

2 Answers2

5

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$.

5xum
  • 123,496
  • 6
  • 128
  • 204
0

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}.$

Somos
  • 35,251
  • 3
  • 30
  • 76