Re: closed form for convolution of a^n with Fibonacci numbers

On 16 Jul 2005 18:17:53 -0700, "hawkmoon269" <rson@xxxxxxxxxx> wrote:

>Thanks for the response. I'm sorry, though...I know the closed form
>and the formula for the sum of a geometric series, but I don't
>understand how this could be done...because I have to compute either
>the n-kth Fibonacci or a^(n-k)...i.e., I don't know how to deal with
>k...

Say f_n is the n-th Fibonacci number. Then that closed form
says

f_n = a b^n + c d^n

where a, b, c, and d are constants involving all sort of square roots,
right?

Now you wanted the convolution of this sequence and the sequence
e_n, where

e_n = g^n

for g some integer.

The convolution would be

h_n = sum_{k=0}^n e_k f_{n-k}.

If you plug in the two formulas for f_n and e_n you see that

h_n = a b^n sum (g/b)^k + c d^n sum (g/d)^k,

where both sums are from k = 0 to k = n.

Those sums are finite geometric series, so you can write
down a closed form for them and you're done.

************************

David C. Ullrich
.

Relevant Pages

  • Re: closed form for convolution of a^n with Fibonacci numbers
    ... Thanks for the response. ... though...I know the closed form ... and the formula for the sum of a geometric series, ...
    (sci.math)
  • Re: number sequence
    ... It is a sequence with the following definition ... The equation can furthur simplified using the sum of geometric series ... Prev by Date: ...
    (sci.math)
  • Re: Limiting Value of Sum of Reciprocals ??
    ... I've a sequence of numbers: ... What is the formula for the sum of "n" terms of the above ... closed form expression for the sum in terms of elementary function, ...
    (sci.math.num-analysis)
  • Re: closed form for convolution of a^n with Fibonacci numbers
    ... then either you know the closed form for the Fibonacci ... If you know how to sum a geometric series, ... If you don't know how to sum a geometric series, ...
    (sci.math)
  • Re: Help with a recursive equation
    ... I was looking for any pointers to the closed form solution of the ... Suppose my first sequence of numbers is just positive integers: ... My second sequence is every 9th member of first sequence ... With the recursion stopping at k=0, ...
    (sci.math)