Click the arrow to go up a level to the Math Index.

Follow the above link or click the graphic below to visit the Homepage.

Special Sums of Generalized Fibonacci Numbers Jim Cullen

---

Brief Introduction to the Generalized Fibonacci Sequences

The Fibonacci sequence and the 'Golden Mean' are fascinating mathematical subjects and have been studied extensively for the better part of two millenia. The prescence and effect of this singular ratio can be found in Art, Science, Nature, Religion, Mathematics, Philosophy, Architecture, and the inner workings of the human mind itself. For the most comprehensive source of information available on the Fibonacci Numbers, the 'Golden Mean', and other related topics, please visit Dr. Ron Knott's Fibonacci Numbers and the Golden Section, sponsored by the Mathematics Department of the University of Surrey, UK.

The Fibonacci Numbers are integers, members of the recursive integer sequence, the Fibonacci Sequence. The sequence begins; { 0, 1, 1, 2, 3, 5, 8, 13, 21, ^{. . .} } and is recursive in that the value of any Fibonacci Number is the sum of the previous two Fibonacci Numbers. Each Fibonacci Number is referenced according to it's ordinal position in the list, with Fibonacci( 0 ), or just F( 0 ), being the first Fibonacci Number in the sequence and having the value zero. The generic variable z will be used as the ordinal and so the recursive property can be stated:

F( z ) = F( z - 1 ) + F( z - 2)

The Fibonacci Sequence is actually just one of an infinite number of integer sequences of this type. Another well-known example is the Lucas Sequence. The Lucas Numbers have the same recursive properties as the Fibonacci Numbers but the Lucas Sequence begins with different values for the first two members of the sequence. The first few Lucas Numbers are; { 2, 1, 3, 4, 7, 11, 18, 29, ^{. . .} }. To reference a Lucas Number we use Lucas( z ), or just L( z ). We can then say that the Lucas Sequence differs from the Fibonacci Sequence in that L( 0 ) = 2 and L( 1 ) = 1 while F( 0 ) = 0 and F( 1 ) = 1. Since there are an infinite number of such sequences that can be identified by the first two values in the sequence, we will use the notation G( z ) to indicate a Generalized Fibonacci Sequence. We will further indicate the starting values of the Generalized Sequence by using G( 0 ) = a and G( 1 ) = b. A specific Generalized Fibonacci Sequence and the ordinal position of interest can then be notated by G( a, b, z ). We can now restate the recursive property of the Fibonacci-type sequences as:

G( a, b, z ) = G( a, b, z - 1 ) + G( a, b, z - 2)

One of the better known properties of the Fibonacci-type sequences ( and one that has generated much philosophical discussion ) is the fact that, as z approaches infinity, the ratio of G( a, b, z ) to G( a, b, z - 1 ) converges on the value of the "Golden Mean" or the "Golden Ratio", an irrational number with a decimal value of approximately 1.61803398875 that has historically been denoted by the Greek letter Phi. In this paper I will use Phi to indicate this value which is equal to:

Phi =

Sqrt( 5 ) + 1 2

and the related value, denoted by phi, which is both the reciprocal of Phi and the value of Phi - 1. Therefore phi has a decimal value of approximately 0.61803398875, and I will use phi to denote this value in this paper. The value of phi is equal to:

phi =

Sqrt( 5 ) - 1 2

The values Phi and (-)phi are the roots of the quadratic x² - x - 1 = 0. To demonstrate, take any pocket calculator and clear the display. Type in any number you may like. Perform this two-step procedure: take the reciprocal ( just press the x^-1 button ) and then simply add one to the answer you get ( press + 1 = ). Repeat the procedure: x^-1 + 1 =, reciprocal, add one, reciprocal, add one, etc. Eventually, the number showing in the display will converge on the value of Phi. When you take the reciprocal of this, then the value of phi will show in the display. Add one to this and you're back to displaying the value of Phi again! Any starting value ( except zero of course ) will result in the convergence of the display results to the values of Phi and phi.

We can use the values of Phi and phi to calculate Fibonacci Numbers directly instead of using the recursive relation to step our way through the Fibonacci Sequence. There are two forms of the equation: one for integer arguments and one for real arguments. The integer form of this equation is called the 'Binet Formula' and it is:

F( z ) =

Phiz - ( -phi )z Sqrt( 5 )

The Binet Formula allows us to calculate F( 0 ), F( 1 ), F( 2 ), and so on. But what if we want to calculate the value of F( 1.5 ) or the value of F( 3/7 )? The second form of the equation allows for arguments that are not integers. The second form of the Fibonacci equation allows us to calculate a Fibonacci number for any real value of z, not just integer values of z. The results involve imaginary numbers but we will only be concerned with the real component of the results for our purposes. This form of the Fibonacci formula is:

Fib( z ) =

Phiz - cos( Pi * z ) * phiz Sqrt( 5 )

I will use the notation F( z ) and Fib( z ) to refer to the above formulas. Either one of these formulas may be utilized to calculate the values for any Generalized Fibonacci Sequence by using the following relation:

G( a, b, z ) =

a * F( z - 1 ) + b * F( z )

There are of course an infinite number of Generalized Fibonacci Sequences, among them are the Fibonacci Sequence itself G( 0, 1, z ) and the Lucas Sequence G( 2, 1, z ).

Having settled on the above definitions, we end the introduction to the Generalized Fibonacci Sequences. For more detailed information, please visit Dr. Ron Knott's Fibonacci Numbers and the Golden Section, the largest and most informative web site on the internet devoted to the study of the Fibonacci and related sequences, the Golden Section, and the Golden String. You may also download the PDF version of the Fibonacci Formulae which provides a much more complete review of mathematical formulae and relations regarding Generalized Fibonacci Numbers. Dr Ron Knott's website has been generously hosted by the Mathematics Department of the University of Surrey, UK.

Hardware support for much of the work on this page includes: Texas Instruments' Voyage-200 PLT ( 12MHz M68000 CPU ) for summations, numerical analysis, and some algebraic operations; Hewlett-Packard's HP49G+ ( 75MHz ARM CPU ) for summations and some algebraic operations; Microsoft Quick-Basic Ver4.5 for generation of tables of high-speed sums and cross-checking. The best stuff, as always, is worked out on pencil and paper ( CPU supplied by user ).


Special Summations of Generalized Fibonacci Sequences

All summations and solutions given elsewhere in the literature will be credited. All other solutions have been developed by myself and, while some of my own solutions may possibly be given previously by another author, my solutions will have been developed independently of their work with no infringement on rights intended.

We begin with a surprisingly elegant observation ( Vajda - 1989) and ( Dunlap - 1997 ) involving summations of the Fibonacci and Lucas Numbers, specifically:

inf     F( i ) 2i = 2 i = 0

inf     L( i ) 2i = 6 i = 0

which can be generalized for any real number ( r ) being raised to the power of i in the denominator. If you graph the results of the following summations, you will find an asymptote at r = Phi since there will be a value of zero in the denominator, resulting in an infinity. There are some useful generalized solutions for these kinds of summations involving the Fibonacci Sequence, such as:

inf   F( i ) ri = r r2 - r - 1 i = 1

inf   F( i - 1 ) ri = 1 r2 - r - 1 i = 1

All summations of this type can be expressed by a generalized form which is:

inf
	F( i + d ) r( i + k )	=	G( 1, r, d + 1 ) rk . ( r2 - r - 1 )
i = 1

Note that, due to the offset d in the Fibonacci Sequence, this form of the solution is true only for the summation beginning at i = 1. The summation beginning at i = 0 requires a separate solution, which is:

inf
	F( i + d ) r( i + k )	=	G( 1, r, d ) r( k - 1 ) . (r2 - r - 1 )
i = 0

and, in fact, for any beginning point of the summation i = m the solution can be found in closed form by:

inf
	F( i + d ) r( i + k )	=	G( 1, r, d + m ) r( m + k - 1 ) . ( r2 - r - 1 )
i = m

The summations given by Vajda and Dunlap, generalized for r, now have the forms:

inf       F( i ) ri = r r2 - r - 1 i = 0

inf       L( i ) ri =   2 + r + 2 r2 - r - 1 i = 0

These particular summations of course involve the Finonacci and Lucas sequences but it is possible to write the summation for any Generalized Fibonacci Sequence. This has already been done and this form of the summation ( Stan Rabinowitz - 1996 ) is:

inf
	G( a, b, i ) ri	=   a +	a + br r2 - r - 1
i = 0

General Forms for Special Summations of Generalized Fibonacci Sequences

My interest in the general form of the summation given by Rabinowitz is that it is possible for the summation to be equal to zero. To explore this situation, I've altered the form of the summation in order to allow the summation to begin at any integer value ( m ) greater than or equal to zero. I've also added into the numerator the constant ( k ), which may be any real number. The new form of the summation is:

inf
	G( a, b, i ) + k ri
i = m

As could have been expected, the sum depends linearly on the value you assign to the constant k with all other values being held constant. The measure of the linear dependence of the sum on the value of k, or the amount of change in the sum per unit change of the value of k, is a value dependent only on the values of r and m. This means that k has the same effect on the sum regardless of the values of a and b which define the Generalized Fibonacci Series in the summation.

The exact expression for the amount of change in the sum for a unit change in the value of k is:

r( 1 - m ) r - 1

This expression being noted, I regarded the effect on the sum of increasing the value of m. Of course the sum decreased, and it decreased in an amount determined by the values of another Generalized Fibonacci Series! What I did from this point was to use this characteristic general series to determine the sum while k was held at the value of zero. At a given value of m, the sum would have a value determined by this series and, using the above expression for the change in the sum per change in k, I was able to determine the proper value of k to cause the sum to equal zero. The intent was to discover under what conditions the sum would equal out to zero. What actually happened however, was that I found something more useful - a formula for the infinite summation that worked. I first determined the value of k to bring the sum to zero, determined by a general fibonacci series:

( 1 - r ) r2 - r - 1

. G[ ( r - 1 ) . b - ( r - 2 ) . a, b + ( r - 1 ) . a, m + 1 ]

which I then used in reverse... for a given k I could determine the difference between the "zero point" and k and, applying the fact that there is a linear change in the sum for this change in k, the sum could be determined. This means you take k and subtract the value above and then multiply by the step change in k. The final result, after just a little rearranging and cancelling, and after determining that:

G[ ( r - 1 ) ^. b - ( r - 2 ) ^. a, b + ( r - 1 ) ^. a, m + 1 ]

is the same as stating:

r ^. G( a, b, m ) + G( a, b, m - 1 )

you are left with the solution that:

inf
	G( a, b, i ) + k ri	= r( 1 - m ) .	[	k r - 1	+	r . G( a, b, m ) + G( a, b, m - 1 ) r2 - r - 1	]
i = m

You may also omit the constant value k from the summation and you are left with:

inf
	G( a, b, i ) ri	=	r . G( a, b, m ) + G( a, b, m - 1 ) r( m - 1 ) . ( r2 - r - 1 )
i = m

which is equivalent to:

inf
	G( a, b, i ) ri	=	G( b + ar - a, br + a, m ) r( m - 1 ) . ( r2 - r - 1 )
i = m

which reduces to the solution given by Rabinowitz when m is set to zero. We can disregard the constant k from here on. These solutions for Generalized Fibonacci Sequences may be solved for the special cases of G( 0, 1, z ) and G( 2, 1, z ), which are the Fibonacci and Lucas sequences respectively but there is little savings in complexity of the solutions in these cases, which are:

inf
	F( i ) ri	= r( 1 - m ) .	[	G( r - 1, 1, m + 1 ) r2 - r - 1	]
i = m

and

inf
	L( i ) ri	= r( 1 - m ) .	[	G( 3 - r, 2 . r - 1, m + 1 ) r2 - r - 1	]
i = m

which can be immediately rewritten in the following forms:

inf
	F( i ) ri	=	r . F( m ) + F( m - 1 ) r( m - 1 ) . ( r2 - r - 1 )
i = m

and

inf
	L( i ) ri	=	r . L( m ) + L( m - 1 ) r( m - 1 ) . ( r2 - r - 1 )
i = m

which are then simply restatements of the general case. Returning to the original solution ( without the constant k in the numerator ), restated here:

inf
	G( a, b, i ) ri	=	r . G( a, b, m ) + G( a, b, m - 1 ) r( m - 1 ) . ( r2 - r - 1 )
i = m

we'll look at the limitations of some of the variables. The variable r must be a real number greater than zero but not equal to Phi since there is an asymptote there for all solutions, resulting in an infinity. The other root of r² - r - 1 is the value -phi which won't concern us here since r is constrained to real numbers greater than zero. The value of m must be an integer and not less than zero. a, b, and k may be any real numbers. There are also some interesting roots for all Generalized Fibonacci Sequences G( a, b, z ) when a is greater than b and m = 0. The roots appear when r = ( a - b ) / a and so are located between zero and one. There is another root but again does not concern us due to the constraints on the variable r.

We could further imagine at this point taking what we already know from the summation given earlier and repeated here:

inf
	F( i + d ) r( i + k )	=	G( 1, r, d + m ) r( m + k - 1 ) . ( r2 - r - 1 )
i = m

and using that knowledge to extend the properties of another summation discussed earlier:

inf
	G( a, b, i ) ri	=	r . G( a, b, m ) + G( a, b, m - 1 ) r( m - 1 ) . ( r2 - r - 1 )
i = m

This would give us the ability to find the closed form solution for summations of the form:

inf
	G( a, b, i + d ) r( i + k )
i = m

We begin by splitting the Generalized Fibonacci summation into its Fibonacci component summations:

inf			inf			inf
	F( i + d ) r( i + k )	=  a .		F( i + d - 1 ) r( i + k )	+  b .		F( i + d ) r( i + k )
i = m			i = m			i = m

and then combining the solutions of the individual summations:

a . G( 1, r, d + m - 1 ) r( m + k - 1 ) . ( r2 - r - 1 )

+

b . G( 1, r, d + m ) r( m + k - 1 ) . ( r2 - r - 1 )

to reveal a closed-form solution for the summation of interest:

inf
	G( a, b, i + d ) r( i + k )	=	a . G( 1, r, d + m - 1 ) + b . G( 1, r, d + m ) r( m + k - 1 ) . ( r2 - r - 1 )
i = m

which is equivalent to:

inf
	G( a, b, i + d ) r( i + k )	=	G( b + ar - a, br + a, d + m ) r( m + k - 1 ) . ( r2 - r - 1 )
i = m

Another Special Summation of Generalized Fibonacci Sequences

Another interesting set of summations, again from ( Vajda - 1989) and ( Dunlap - 1997 ) are given for the Fibonacci and Lucas Sequences:

inf     i . F( i ) 2i = 10 i = 0;1

inf     i . L( i ) 2i = 22 i = 0;1

which, for the Fibonacci Sequence, has one useful form of generalization as follows:

inf       i . F( i ) ri = r3 + r ( r2 - r - 1 )2 i = 0;1

inf       i . F( i - 1 ) ri = 2r2 - r ( r2 - r - 1 )2 i = 0;1

and can be used to rewrite the expressions for Generalized Fibonacci Sequences by splitting the Generalized Sequence summation into its Fibonacci Sequence components and noting that:

a ^. ( 2r² - r ) + b ^. ( r³ + r ) = r ^. ( br² + 2ar + b - a )

The final result is the generalized form of the summation as given by Rabinowitz ( 1996 ):

inf
	i . G( a, b, i ) ri	=	r . ( b r2 + 2 a r + b -a ) ( r2 - r - 1 )2
i = 0;1

In the above summations, I've used i=0;1 to indicate that the summation gives identical answers whether we start the summation at zero or one. The numerical results may be identical but the general solution, if one exists in closed form, will consist of two different algebraic statements that give numerically identical results. Another useful summation of this type is:

inf
	i . F( i + d ) ri	=	G( r3 + r, r3 + 2r2, d ) ( r2 - r - 1 )2
i = 0;1

and, like any summation of this variety where i is a factor in the numerator, gives the same answer whether the summation begins at zero or one. The solution is equivalent to:

inf
	i . F( i + d ) ri	=	r . G( r2 + 1, r2 + 2r, d ) ( r2 - r - 1 )2
i = 0;1

Again my interest was to uncover the generalized form of the summation, given previously by Rabinowitz, in order to allow the summation to begin at any integer value m greater than or equal to zero. This time however, no constant was added into the summation. The new form of the summation would then be:

inf
	i . G( a, b, i ) ri
i = m

Based on numerical analysis that provided integer results, I took a stab at the form of the solution for the summation which turned out to be:

inf
	i . G( a, b, i ) ri	=	p( r ) . G( a, b, m ) + q( r ) . G( a, b, m + 1 ) r( m - 1 ) . ( r2 - r - 1 )2
i = m

with an obvious extended form of:

inf
	i . G( a, b, i + d ) r( i + k )	=	p( r ) . G( a, b, d + m ) + q( r ) . G( a, b, d + m + 1 ) r( m + k - 1 ) . ( r2 - r - 1 )2
i = m

and an alternate form based on G( a, b, m - 1 ) instead of G( a, b, m + 1 ) which is:

inf
	i . G( a, b, i + d ) r( i + k )	=	p( r ) . G( a, b, d + m ) + q( r ) . G( a, b, d + m - 1 ) r( m + k - 1 ) . ( r2 - r - 1 )2
i = m

with p( r ) and q( r ) being functions of r producing the observed integers in the numerical analysis.I substituted in ascending values of m and r and then had the computer do the search for combinations of integer values for p( r ) and q( r ) that satisfied the known value for the summation (calculated numerically). The results revealed a pattern dependent on r and were, in part, as follows:

r = 2: [ 1 * 1 * m + 3 ] * F( m ) + [ 1 * m + ( 5 - 0 ) ] * F( m + 1 )
r = 3: [ 5 * 2 * m + 5 ] * F( m ) + [ 5 * m + ( 11 - 1 ) ] * F( m + 1 )
r = 4: [ 11 * 3 * m + 7 ] * F( m ) + [ 11 * m + ( 19 - 2 ) ] * F( m + 1 )
r = 5: [ 19 * 4 * m + 9 ] * F( m ) + [ 19 * m + ( 29 - 3 ) ] * F( m + 1 )

with the series 1, 5, 11, and 19 appearing as results of ( r² - r - 1 ) being applied to the r-values of 2, 3, 4, and 5. The final formula followed soon after with random testing after that for non-integer values (+/-) for a, b, m and r. The final form of the solution turns out to be:

inf
	i . G( a, b, i ) ri	=	p( r ) . G( a, b, m ) + q( r ) . G( a, b, m + 1 ) r( m - 1 ) . ( r2 - r - 1 )2
i = m
with
p( r ) = m r3 - 2 m r2 + 2 r + m - 1
and
q( r ) = ( m + 1 ) r2 - m r - m + 1

with the alternate solution, based on G( a, b, m - 1 ) instead of G( a, b, m + 1 ), being as follows:

inf
	i . G( a, b, i ) ri	=	p( r ) . G( a, b, m ) + q( r ) . G( a, b, m - 1 ) r( m - 1 ) . ( r2 - r - 1 )2
i = m
with
p( r ) = m r3 + ( 1 - m ) r2 + ( 2 - m ) r
and
q( r ) = ( m + 1 ) r2 - m r - m + 1

and the obvious extended form given earlier remains with p( r ) and q( r ) unchanged:

inf
	i . G( a, b, i + d ) r( i + k )	=	p( r ) . G( a, b, d + m ) + q( r ) . G( a, b, d + m - 1 ) r( m + k - 1 ) . ( r2 - r - 1 )2
i = m
with
p( r ) = m r3 + ( 1 - m ) r2 + ( 2 - m ) r
and
q( r ) = ( m + 1 ) r2 - m r - m + 1

This form of the solution is preferred though it does not generalize well for solutions of summations where the factor i in the numerator is raised to a power k. This form of the solution to the summation would have the general form:

inf
	ik . G( a, b, i ) ri	=	p( r ) . G( a, b, m ) + q( r ) . G( a, b, m - 1 ) r( m - 1 ) . ( r2 - r - 1 )k+1
i = m

with p(r) and q(r) being polynomials of increasing order with k. As an example, for the specific case of k=2, the solution is:

inf
	i2 . G( a, b, i ) ri	=	p( r ) . G( a, b, m ) + q( r ) . G( a, b, m - 1 ) r( m - 1 ) . ( r2 - r - 1 )3
i = m
with
p( r ) = m2r5 + ( -2m2 + 2m + 1 )r4 + ( -m2 + 2m + 5 )r3 + ( 2m2 - 6m + 3 )r2 + ( 2 - m )2 r
and
q( r ) = ( m + 1 )2r4 + ( -2m2 - 2m + 1 )r3 + ( 6 - m2 )r2 + ( 2m2 - 2m - 1 )r + ( m - 1 )2

To anyone who has ever attempted polynomial approximations to recursive sequences, these polynomials should look very familiar. As we increase the k in the numerator's i^k factor, the polynomials quickly grow in size until the solution polynomials for even moderate values of k fill an entire sheet by themselves. The polynomials do exhibit a pattern however, and this pattern suggests a general solution involving recursive sequences of an unusual variety.

This document is in progress...


URL: https://jcullen88.github.io/CullenGenealogyHomepage/Math3.html
© 2004 - 2006: Jim Cullen - all rights reserved.
Last Update: October 03, 2006.

---

Use your Back Button or click here to go to the Math Index