Fibonacci numbers in decimal expansions
Dave L. Renfro
Recall that the Fibonacci sequence is defined by
F(n+2) = F(n+1) + F(n) with F(1) = F(2) = 1,
which gives
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,
233, 377, 610, 987, 1597, 2584, 4181, 6765,
10946, 17711, 28657, 46368, 75025, 121393, ...
Now consider the decimal expansions of
10^B / [10^(2B) - 10^B - 1]
for B = 2, 3, 4, 5:
--------------------------------------------------
B = 2
100/9899 = 0. 01 01 02 03 05 08 13 21 34 55 90 46 ...
--------------------------------------------------
B = 3
1000/998999 = 0. 001 001 002 003 005 008 013 021 034
055 089 144 233 377 610 988 599 ...
--------------------------------------------------
B = 4
10000/99989999 = 0. 0001 0001 0002 0003 0005 0008 0013
0021 0034 0055 0089 0144 0233 0377 0610 0987 1597 2584
4181 6766 0947 ...
--------------------------------------------------
B = 5
100000/9999899999 = 0. 00001 00001 00002 00003 00005
00008 00013 00021 00034 00055 00089 00144 00233 00377
00610 00987 01597 02584 04181 06765 10946 17711 28657
46368 75026 21394 ...
--------------------------------------------------
As you can see, the decimal expansion for B = k (at least,
for k = 2, 3, 4, 5) gives an initial finite subsequence
of the Fibonacci sequence when the decimal expansion
is separated into B-length blocks of digits, with the
first incorrect entry (seemingly always a close miss)
occuring for the largest B-digit Fibonacci number.
I'm pretty sure this holds for all larger integer values
of B, but I haven't given any thought as to how one might
prove this.
This result is given in the following paper, but I don't
know if the result is proved in this paper.
Mike Keith, "Stalking the wild fraction", Recreational and
Educational Computing 13 #4 (January-February 1999), 4-7 & 14.
I learned about this paper from a short summary given by
Raymond N. Greenwell on pp. 73-74 of the "Media Highlights"
column in College Mathematics Journal 31 #1 (January 2000).
[Warning: The displayed equation at the bottom of p. 73
appears to have k_1 and k_2 reversed (based on my testing
of the formula).]
In fact, the following more general result for 2-term recursive
sequences is given (proved?) in Keith's paper.
Let a, b, r, and s be positive integers. Define the sequence
f(n) recursively by
f(n+2) = r*f(n+1) + s*f(n) with f(1) = a and f(2) = b
Then arbitrarily long initial finite subsequences of the
sequence f(1), f(2), f(3), ... appear, for sufficiently large
positive integer values of B, in the initial B-blocks of the
decimal expansion of the number
[a*10^B + (b - ar)] / [10^(2B) - r*10^B - s]
As an example, let's look at the case where a = 4, b = 12,
r = 3, and s = 7. That is, the sequence defined by
f(n+2) = 3*f(n+1) + 7*f(n) with f(1) = 4 and f(2) = 12,
which gives
4, 12, 64, 276, 1276, 5760, 26212, 118956, ...
We are thus led to consider the decimal expansion of
[4*10^B + (12 - 4*3)] / [10^(2B) - 3*10^B - 7],
which I'll display for B = 3, 4, 5.
--------------------------------------------------
B = 3
4000/996993 = 0. 004 012 064 277 281 ...
--------------------------------------------------
B = 4
40000/99969993 = 0. 0004 0012 0064 0276 1276 5762 6223 ...
--------------------------------------------------
B = 5
400000/9999699993 = 0. 00004 00012 00064 00276 01276
05760 26213 18961 ...
--------------------------------------------------
As another example, let's look at the case where a = 2,
b = 7, r = 1, and s = 3. That is, the sequence defined by
f(n+2) = f(n+1) + 3*f(n) with f(1) = 2 and f(2) = 7,
which gives
2, 7, 13, 34, 73, 175, 394, 919, 2101, 4858,
11161, 25735, 59218, ...
We are thus led to consider the decimal expansion of
[2*10^B + (7 - 2*1)] / [10^(2B) - 1*10^B - 3],
which I'll display for B = 2, 3, 4.
--------------------------------------------------
B = 2
205/9897 = 0. 02 07 13 34 74 79 ...
--------------------------------------------------
B = 3
2005/998997 = 0. 002 007 013 034 073 175 394 921 105 ...
--------------------------------------------------
B = 4
20005/99989997 = 0. 0002 0007 0013 0034 0073 0175 0394
0919 2101 4859 1163 ...
--------------------------------------------------
Dave L. Renfro
The Qurqirish Dragon
Those entries aren't incorrect! note this (for B=2, but this appears
to hold for the others also):
> B = 2
>
> 100/9899 = 0. 01 01 02 03 05 08 13 21 34 55 90 46 ...
the first "error" is the 90, correct? actually, if you look at it like
this:
89(+1) 44(+2) 33 ...
You see, there isn't an error, just a carry over from the next term,
which has too many digits to be the next "pair"
Similarly:
> B = 3
>
> 1000/998999 = 0. 001 001 002 003 005 008 013 021 034
>
> 055 089 144 233 377 610 988 599 ...
This is correct up to 610, and then:
987(+1) 597(+2) 584 ...
again, it is correct, when you consider the need for more than 3
digits for later terms, so the earlier digits carry over.
Granted, once the number of digits in F(n) is more than twice the
grouping, the carries are so large that the sequence will be
unrecognizable.
Also note that if you made the numerators 1 (rather than 10^B), you
are simply adding a set of 0's to the start of the decimal (consider
F(0)=0, and this still gives the Fibonacci sequence). This might make
further analysis easier for you.
JEMebius
1 / (1 - x - x^2) = 1 + x + 2x^2 + 3x^3 + 5x^4 + ...
for all real and complex x with |x| < 1.
Johan E. Mebius
Rob Johnson
This is because the generating function of the Fibonacci Series is
1 2 3 4 5 6 7
------- = 1 + 1 + 2x + 3x + 5x + 8x + 13x + 21x + ...
1-x-x^2
To explain your resule, stick in x = 10^{-n} and multiply numerator and
denominator by 10^{2n} (not 10^n as your post suggests). That is
10^(2B) / [10^(2B) - 10^B - 1]
Rob Johnson <r...@trash.whim.org>
take out the trash before replying
to view any ASCII art, display article in a monospaced font
Rob Johnson
Typo: the second term in the series should be x, not 1. That is,
1 2 3 4 5 6 7
------- = 1 + x + 2x + 3x + 5x + 8x + 13x + 21x + ...
1-x-x^2
Rob Johnson <r...@trash.whim.org>
Rob Johnson
Furthermore, there is no reason that the numerator cannot be as Dave
originally suggested: 10^B. This just shifts the series B digits to
the right, moving the first term to the fractional part. Thus,
10^B / [10^(2B) - 10^B - 1]
works just fine. Sorry about suggesting otherwise.
Gottfried Helms
> Here's something neat I came across recently.
>
> Recall that the Fibonacci sequence is defined by
>
> F(n+2) = F(n+1) + F(n) with F(1) = F(2) = 1,
>
> which gives
>
> 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,
>
> 233, 377, 610, 987, 1597, 2584, 4181, 6765,
>
> 10946, 17711, 28657, 46368, 75025, 121393, ...
>
> Now consider the decimal expansions of
>
> 10^B / [10^(2B) - 10^B - 1]
>
Very nice...
I first try to get more familiar with it:
cancel to get p(b) = 1/(10^b - 1 - 1/10^b)
If I expand p(b) into a taylor-series - this can be done
by the simple reformulation as geometric series:
- 1
p(b) = ------------------ = - ( 1 + (10^b-10^-b) + (10^b - 10^-b)^2 + ...)
1 - (10^b - 10^-b)
and then collect like powers of 10 into columns:
1
+ (1*10^b -1*10^-b)
+ (1*10^2b -2 +1*10^-2b)
+ 1*10^3b -3*10^b +3*10^-b -1*10^-3b
+1*10^3b -4*10^2b +6 -4*10^-2b +1*10^-4b
+...
then I think the vertical columns give divergent sums which can be
expressed as binomials/fibonacci numbers at the b*k'th powers of 10.
I do not yet see, how the positive b'th powers of 10 cancel with the negative
b'th powers, but it would be interesting to see this.
As b increases the number of digits for the representation of the fibonacci-
numbers in the "slots" increase; that -at least- is obvious.
Let us know how you proceed...
Gottfried
Gottfried Helms
>
> Very nice...
> I first try to get more familiar with it:
Just find the other answers after finished editing - the
generating-function for the fibonacci-numbers as given
by Johan and Rob was a much better key for that observation.
Gottfried
Dave L. Renfro
> 1 / (1 - x - x^2) = 1 + x + 2x^2 + 3x^3 + 5x^4 + ...
> for all real and complex x with |x| < 1.
O-K, I've seen this before and it makes the result seem
less "pi in the sky". Originally, the result seemed to me
almost as if it could have been an April Fool's day joke.
Gary Litvin has posted a reply about this generating function
in the ap-calculus discussion group (archived at Math Forum).
By the way, you've probably already realized this, but the
ratio test and a standard result about the limiting ratio
of successive Fibonacci numbers implies that the radius of
convergence is 1/phi < 1.
ap-calculus [Gary Litvin; 19 November 2010]
http://mathforum.org/kb/message.jspa?messageID=7291088
Dave L. Renfro
JEMebius
Dear Dave,
My thanks for your comment. I was too fast again in my reply. Of course the radius of
convergence is not 1, but 1/phi.
What about a similar exercise for the Plastic Number, a ratio occurring in the work of the
Dutch architect Dom Hans van der Laan!
The Plastic Number is by definition the real root of the equation ?x: x^3 = x + 1.
It is very loosely speaking the 3D counterpart of the Golden Ratio, which manifests itself
in the plane.
See for instance http://en.wikipedia.org/wiki/Plastic_number , and for Hans van der Laan:
http://nl.wikipedia.org/wiki/Hans_van_der_Laan_(architect) .
Problem for all interested persons, 1 / (1 - x^2 - x^3) = ?
Could the coefficients of this generating function appear as figurate numbers in some 3D
construction related to the buildings designed by Hans van der Laan?
Ciao: Johan E. Mebius
David Bernier
I'll have a go at starting things.
f(x) . (1 - x^2 - x^3) = 1 : When using generating functions,
multiplying by 'x' accomplishes some form of right-translation by
one unit for the coefficients. In matrix form, say 20x20,
it's linear and I imagine this corresponds to partial information
on what happens to the coefficients; it's partial because it
only covers the coefficients for x^0, x^1, ... x^19 [20
of them, and no more for 20x20].
There should be 19 1's matching this mock-action of multiplying
by 'x' on N, N = {0, 1, 2, 3 ...} .
It's a "mock-action" because one associates f: N-> N with
f(n) = successor(n), and 0 isn't the successor of any element of N.
Multiplying by x^2 is the same as multiplying by 'x' twice.
I'm not sure what these matrices are called for 20x20 or
other matrix dimensions, but the mental picture
for a unit-shift would seem to be ones on the diagonal
just above the main diagonal when a matrix M acts on
a column-vector v via v |-> Mv , the customary convention.
f(x) . (1 - x^2 - x^3) in matrix form should have
ones on the main diagonal, and -1 's on the
smaller diagonal two rows up, with also
-1 's on the smaller diagonal three rows up.
The coefficients of the "mock-action" matrix M are
all known and are here one of 0, +1 or -1.
I think det(M) =/= 0, so M has an inverse.
f(x) . (1 - x^2 - x^3) = 1 .
Translating to linear algebra, this would translate as:
M.x = v_0 . and v_0 is the 20x1 column-vector: [1, 0, 0, ... 0].
M is invertible (I think) . So x = (M^{-1}). v_0 .
That way, if this is anywhere near correct, linear algebra
can be used to study this for K x K matrices,
with K large in computations, or arbitrarily large in
theory. I'm not sure if this has advantages over
characteristic equations, as with the Fibonacci recurrence.
> Could the coefficients of this generating function appear as figurate
> numbers in some 3D construction related to the buildings designed by
> Hans van der Laan?
>
> Ciao: Johan E. Mebius
--
$ gpg --fingerprint davi...@videotron.ca
pub 2048D/653721FF 2010-09-16
Key fingerprint = D85C 4B36 AF9D 6838 CC64 20DF CF37 7BEF 6537 21FF
uid David Bernier (Biggy) <davi...@videotron.ca>
Rob Johnson
JEMebius <jeme...@xs4all.nl> wrote:
>What about a similar exercise for the Plastic Number, a ratio occurring in the work of the
>Dutch architect Dom Hans van der Laan!
>The Plastic Number is by definition the real root of the equation ?x: x^3 = x + 1.
>It is very loosely speaking the 3D counterpart of the Golden Ratio, which manifests itself
>in the plane.
>See for instance http://en.wikipedia.org/wiki/Plastic_number , and for Hans van der Laan:
>http://nl.wikipedia.org/wiki/Hans_van_der_Laan_(architect) .
>
>
>Problem for all interested persons, 1 / (1 - x^2 - x^3) = ?
>Could the coefficients of this generating function appear as figurate numbers in some 3D
>construction related to the buildings designed by Hans van der Laan?
To get the power series for the generating function, set
oo
--- k
1 = (1 - x^2 - x^3) > a x [1]
--- k
k=0
Rearranging terms in [1], we get
oo
2 --- k
1 = a + a x + (a - a ) x + > (a - a - a ) x [2]
0 1 2 0 --- k k-2 k-3
k=3
Thus, we get
a = 1 a = 0 a = 1 [3a]
0 1 2
and for k > 2,
a = a + a [3b]
k k-2 k-3
The radius of convergence of the series for the generating function
is the reciprocal of the Plastic Number defined above. That is, the
radius of convergence is approximately 0.75487766624669276.
Furthermore, the Plastic Number is the ratio of successive terms in
the series for which 1/(1 - x^2 - x^3) is the generating function.
I have no idea about the buildings designed by Hans van der Laan.
Dave L. Renfro
with those numerical patterns, and I made use of the comments
that others have made.
Here's the situation (notation slightly changed).
Let a, b, r, and s be positive integers. Define the sequence
{x_n} for n = 0, 1, 2, ... recursively by
x_(n+2) = r*x_(n+1) + s*x_n with x_0 = a and x_1 = b
Then arbitrarily long initial finite subsequences of the
sequence x_0, x_1, x_2, ... appear, for sufficiently large
positive integer values of B, in the initial B-blocks of the
decimal expansion of the number
[a*10^B + (b - ar)] / [10^(2B) - r*10^B - s].
To see why, we first note that the power series expansion of
[a + (b - ar)x] / [1 - rx - sx^2]
about x = 0 is
x_0 + (x_1)x + (x_2)x^2 + (x_3)x^3 + (x_4)x^4 + ...
I will give a formal algebraic derivation of this below.
Now put x = 10^(-B). Then the rational function becomes
the number
[a + (b - ar)*10^(-B)] / [1 - r*10^(-B) - s*10^(-2B)]
Multiplying numerator and denominator by 10^(2B) and
factoring out 10^B (from the numerator) gives the number
10^B * [a*10^B + (b - ar)] / [10^(2B) - r*10^B - s].
Up to a certain point, the initial terms of the
Taylor expansion about x = 0 can be identified with
the initial B-blocks of the decimal expansion of the
above number, since
x_0 + (x_1)x + (x_2)x^2 + (x_3)x^3 + (x_4)x^4 + ...
becomes
x_0 + (x_1)*10^(-B) + (x_2)*10^(-2B) + (x_3)*10^(-3B) + ...
As long as the integers x_0, x_1, x_2, ... have less than
B digits, the integers will appear within consecutive
B-blocks of the decimal expansion, separated by one or
more zeros. Some of the integers that have exactly B digits
may also appear within the B-blocks, but the largest such
integer with B digits will be affected by the "overspill"
of the first such integer having more than B digits, since
an integer with more than B digits will not fit into a
B-block of digits (or something like this).
Finally, we can dispense with the 10^B factor above,
since this will simply move the decimal point by B places
and thus will not affect the "B-blocks of digits pattern"
we're trying to account for. Thus, we can use the number
[a*10^B + (b - ar)] / [10^(2B) - r*10^B - s],
which is the number I originally posted.
----------------------------------------------------
To formally verify by algebra that the Taylor expansion of
[a + (b - ar)x] / [1 - rx - sx^2]
about x = 0 is
x_0 + (x_1)x + (x_2)x^2 + (x_3)x^3 + (x_4)x^4 + ...,
assume the expansion of
[a + (b - ar)x] / [1 - rx - sx^2]
about x = 0 is given by
a_0 + (a_1)x + (a_2)x^2 + (a_3)x^3 + (a_4)x^4 + ...
Now multiply both sides by 1 - rx - sx^2 to get
a + (b - ar)x = (1 - rx - sx^2)(a_0 + (a_1)x + (a_2)x^2 + ...)
= a_0 + (a_1)x + (a_2)x^2 + (a_3)x^3 + (a_4)x^4 + ...
- r*(a_0)x - r*(a_1)x^2 - r*(a_2)x^3 - r*(a_3)x^4 - ...
- s*(a_0)x^2 - s*(a_1)x^3 - s*(a_2)x^4 - ...
Equating coefficients gives
a = a_0
(b - ar) = a_1 - r*(a_0)
0 = a_2 - r*(a_1) - s*(a_0)
0 = a_3 - r*(a_2) - s*(a_1)
0 = a_4 - r*(a_3) - s*(a_2)
*
*
*
0 = a_(n+2) - r*a_(n+1) - s*a_n
*
*
*
Thus, the sequence a_0, a_1, a_2, ... satisfies
a_(n+2) = r*a_(n+1) + s*a_n with a_0 = a and a_1 = b,
and so the sequence a_0, a_1, a_2, ... is identical
to the sequence x_0, x_1, x_2, ...
----------------------------------------------------
Incidentally, simply carrying out the above steps for
(linear poly.) / (quadratic poly.)
results in an expansion whose coefficients satisfy
a 2-term linear constant coefficient recursion relation,
and from this the appropriate identifications can be
made with the given sequence, x_(n+2) = r*x_(n+1) + s*x_n
with x_0 = a and x_1 = b, to come up with
[a + (b - ar)x] / [1 - rx - sx^2].
Indeed, this is how I came up with this rational function.
Also, we can assume the constant coefficient in the quadratic
polynomial is 1 by dividing numerator and denominator of
(linear poly.) / (quadratic poly.) by this coefficient,
which I assumed wasn't zero.
See also "2.2 Rational generating function" at
http://en.wikipedia.org/wiki/Recurrence_relation
Dave L. Renfro
Dave L. Renfro
curious decimal expansions that were based on comments
made on pp. 73-74 of the "Media Highlights" column in
College Mathematics Journal 31 #1 (January 2000).
Fibonacci numbers in decimal expansions [19 & 24 November 2010]
http://groups.google.com/group/sci.math/msg/69f5017c6c79eee1
http://groups.google.com/group/sci.math/msg/a4ce67d678e1473d
Well, a couple of days ago I came across a paper in
the same journal that goes through this in the special
case of the Fibonacci sequence:
James Smoak and Thomas J. Osler, "A magic trick from Fibonacci",
College Mathematics Journal 34 #1 (January 2003), 58-60.
The earlier "Media Highlights" item isn't mentioned at all
(strange that at least one referee or journal editor didn't
notice this), so I don't know if Smoak/Osler came up with
the idea themselves or if the paper was inspired by the
previous "Media Highlights" item.
A .pdf file of the Smoak/Osler paper is freely available at
http://www.rowan.edu/open/depts/math/osler/my_papersl.htm
(it's paper #46 at this web page)
I've known about Osler's neat collection of papers at his
web page for several years, but obviously I haven't looked
through all of them since I would have remembered the
Fibonacci decimal expansion curiosities.
Dave L. Renfro