Sequence relating to Pell numbers; a new technique

[Mitchell Harris]

On Sun, 3 Oct 2004 creigh at o2online.de wrote:

>Thank you for that comment! 
>
>Using the new technique described in the last posting on another ex.,
>I get:  A022095(n) = 2Fib(n) + Fib(n+5)
>Name A022095:  Fibonacci sequence beginning 1 5.
>
>Surely this relation is already known...?

Any 2nd order linear recurrence with constant coefficients is a linear 
combination of successive Fibonacci #'s:

Let G(n) = a G(n-1) + b G(n-2), with G(0) and G(1) the given base cases 
(i.e. constants but... er... variable).

Then G(n) happens to be 
  G(1) F(n) + G(0) F(n-1) (proof by induction)

so in one sense, all this playing around with such recurrences is like 
playing around with addition: given two random 10 digits #'s, it is 
unlikely that their addition has ever been computed before.

so
1) this relation may not have ever been written down before (if that's 
what you mean by "is already known") (so it's new)
2) but that's not surprising, because any particular identity wil not be 
terribly earth shattering. (so it's not really new)
3) but it's how you're using these things (these new but not new 
things) that is/can be interesting.

>
>Sincerely, 
>Creighton 
>
>>Remember that P(n) can be computed with the help of the general >formula for 
>computing the convergents. Thus, 
>>
>>P(n+2) = 2 P(n+1) + P(n) 
>>
>>and the formula above can be written: 
>>a(n) = 1/2 * ( P(n+2) + 3 P(n+1) - 1) 
>>
>>or (by substituting again): 
>>a(n) = 1/2 * ( 5 P(n+1) + P(n) - 1) 
>>
>>Regards, 
>>
>

-- 
Mitch Harris
Lehrstuhl fuer Automatentheorie, Fakultaet Informatik
Technische Universitaet Dresden, Deutschland
http://lat.inf.tu-dresden.de/~harris