Developing a Nonrecursive, Binomial Gibonacci Function
Having come to understand that a function can describe the values of Gibonacci sequence not equal to 2^(n-p), we now have the ability to expand our generalization of the Gibonacci numbers.
Let us generalize some results for Gibonacci Sequences:
For p>0, the pth Gibonacci sequence, f(p,n)
f(p,n)=0 when n < p-1
f(p,n)=1 when n = p-1
and then
f(p,n)=2^(n-p) when n >= p up to n < 2p
the above statement is equivalent to saying that the pth Gibonacci sequence, f(p,n) contains p numbers equal to 2^(n-p)
But when n >= 2p,
f(p,n) < 2^(n-p)
And we have now determined that the amount by which f(p,n) < 2^(n-p) is provided by another function, one derived to produce the roots of Chebyshev Polynomials.
We have seen that, for the next p+1 values in f(p,n), :
f(p,n) + A = 2^(n-p) where n >= 2p and n < 3p+1
Where A is the First Order Chebyshev function.
Likewise, we have seen that function A eventually [when n >= 3p+1] "overcompensates" and adds too much value. The corresponding "overage" is predicted by the second Chebyshev polynomial, given below by B. So, when 3p+1 <= n < 4p-2:
f(p,n) + A - B = 2^(n-p) where n >= 3p+1 and n < 4p+2
and this pattern or alternating adding and subtracting Chebyshev Roots continues:
f(p,n) + A - B + C = 2^(n-p)
where n >= 4p+2 and n < 5p+3
f(p,n) + A - B + C - D = 2^(n-p)
where n >= 5p+3 and n < 6p+4
f(p,n) + A - B + C - D + E = 2^(n-p)
where n >= 6p+4 and n < 7p+5
and so on...
We now revisit the formula Dr. Janjic gave us on the previous page, to produce the roots of Chebyshev Polynomials:
where, using his notation of inner variables, different values of n and k produce A, B, C, D, E, et cetera, above.
This function will be the internal function of an outer summation that represents A + B - C + D - E + F - G....
Again, this is for values of f(p,n), where n is greater than or equal to 2p.
Because of the convention of this work, where each Gibonacci sequence contains zeros from n=0 to n=p-2, and f(p,n)=1 when n=p-1, there is required an offset in our internal counting variables of p+1, such that, for f(p,n) where n=2p, the internal counting variable is equal to 1 (one). Therefore, for the outer summand, the range is given by (n-p+1)/(p+1). The integer part of this statement controls how many terms A + B - C + D -... are required to perform for the correct summation:
when n = 2p, (n-p+1)/(p+1) = 1
when n=3p+1, (n-p+1)/(p+1) = 2
when n=4p+2, (n-p+1)/(p+1) = 3
when n=5p+3, (n-p+1)/(p+1) = 4
and so on...
this means that :
Next, we change the internal variables of Dr. Janjic's formula, simply so we do not get confused, changing the names of the internal variable where m=n and j=i:
Before we can combine the two functions, we need to resolve what values we pass from the outer summand into the internal Chebyshev function. If we look back to the page with the differences, we notice that for the pth Gibonacci sequence, f(p,n), we require p+1 terms from each of the (n-p+1)/(p+1) Chebshev Polynomial root functions. As such, we make the substitution on the inner summand where m= n-(p(i+1)) and k = i.
When n=2p, i=1, m= n-(p(i+1)) = 0
When n=2p+1, i=1, m= n-(p(i+1)) = 1
When n=2p+2, i=1, m= n-(p(i+1)) = 2
... and so on ...
When n=3p+1, i ranges from 1 to 2, when i=2, m= n-(p(i+1)) = 1
When n=3p+2, i ranges from 1 to 2, when i=2, m= n-(p(i+1)) = 2
... and so on ...
Now we plug the two summations in together, where m= n-(p(i+1)) and k = i:
The above function then becomes the general form of a binomial description of Gibonacci Numbers. The above function is not recursive, per se. In computational terms, we have obviated the resursive loop for that of a nested for loop. The results is harder to work with, to be certain. It is nonetheless mathematically interesting, no?
