Let F k ( 1 7 2 9 ) denote the kth Fibonacci 1729-step number . Find
lo g 2 ( k = 1 ∑ ∞ 2 k F k ( 1 7 2 9 ) )
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Proof of ( ∗ ) :
The case n = 2 (usual Fibonacci sequence), I believe, is pretty well known (?) . Here, I will prove for general positive integer n .
( 1 − x − … − x n ) ( k = 1 ∑ ∞ F k ( n ) x k ) = k = 1 ∑ ∞ F k ( n ) x k − k = 1 ∑ ∞ F k ( n ) x k + 1 − … − k = 1 ∑ ∞ F k ( n ) x k + n
All the
F k ( n ) x k − F k − 1 ( n ) x k − … − F k − n ( n ) x k = F k ( n ) x k − i = 1 ∑ n F k − i ( n ) x k
disappear for k > n since F k ( n ) = i = 1 ∑ n F k − i ( n ) by definition, leaving
k = 1 ∑ n F k ( n ) x k − k = 1 ∑ n − 1 F k ( n ) x k + 1 − … − k = 1 ∑ 1 F k ( n ) x k + n − 1
Expanding the sums and doing a slight rearrangment of terms, we arrive at
F 1 ( n ) ( x − x 2 − … − x n ) + F 2 ( n ) ( x 2 − x 3 − … − x n ) + … + F n ( n ) x n = ( x − x 2 − … − x n ) + ( x 2 − x 3 − … − x n ) + … + 2 n − 2 x n = x
because F 1 ( n ) = 1 and F k ( n ) = 2 k − 2 for all 2 ≤ k ≤ n . You will see that the terms eventually cancel out.
After that arduous journey of algebraic manipulation, we finally get that
( 1 − x − … − x n ) ( k = 1 ∑ ∞ F k ( n ) x k ) = x
and thus
g ( x , n ) = k = 1 ∑ ∞ F k ( n ) x k = 1 − x − … − x n x
(I hate the world.)
Log in to reply
You could try to derive a general formula for the sequence:
F n = j = 1 ∑ p F n − j k j
If you want to torture yourself again?
Log in to reply
I might be doing a generalisation of this result for SMPF :D
Log in to reply
@Jake Lai – Its gonna fail in Creativity and originality Applicability and relevance. And you need to pay so much... I don't know for your school but my school never pays for us to represent them in maths or science. Except for crappy NSC, which nobody want's to go because of it's stupid and biased way of judging.
first, let
F
k
(
1
7
2
9
)
=
R
k
first we note that,
R
k
+
R
k
+
1
+
R
k
+
2
+
.
.
.
.
.
R
k
+
1
7
2
8
=
R
k
+
1
7
2
9
now. let
S
=
2
R
1
+
4
R
2
+
8
R
3
+
1
6
R
4
.
.
.
.
.
we now calculate
S
=
2
S
=
4
S
=
.
.
.
.
.
2
1
7
2
8
S
=
2
R
1
R
1
2
R
1
.
.
.
2
2
7
2
7
R
1
+
4
R
2
+
2
R
2
+
R
2
.
.
.
.
.
.
.
.
.
.
.
.
.
+
2
2
7
2
6
R
2
+
8
R
3
+
4
R
3
+
2
R
3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
+
R
2
7
2
8
+
1
6
R
4
.
.
.
.
.
+
8
R
4
.
.
.
.
.
+
4
R
4
.
.
.
.
.
.
.
.
.
.
.
+
2
R
1
7
2
9
+
4
R
1
7
3
0
.
.
.
.
.
note that
2
n
+
2
n
−
1
+
2
n
−
2
+
.
.
.
.
.
.
+
2
+
1
=
2
n
+
1
−
1
adding all 1729 equations
(
2
1
7
2
9
−
1
)
S
=
(
2
1
7
2
8
−
1
)
R
1
+
(
2
1
7
2
7
−
1
)
R
2
.
.
.
.
.
.
+
(
2
−
1
)
R
1
7
2
8
+
2
R
1
+
R
2
+
R
3
.
.
.
.
.
.
+
R
1
7
2
9
+
4
R
2
+
R
3
+
R
4
.
.
.
.
.
.
+
R
1
7
3
0
.
.
.
.
.
.
.
re-writing,
(
2
1
7
2
9
−
1
)
S
=
2
1
7
2
8
R
1
+
2
1
7
2
7
R
2
+
.
.
.
.
.
+
2
R
1
7
2
8
−
(
R
1
+
R
2
+
R
3
.
.
.
.
.
.
+
R
1
7
2
8
)
+
2
R
1
7
3
0
+
4
R
1
7
3
1
.
.
.
for subtraction,
2
∗
2
1
7
2
8
S
=
2
2
7
2
8
R
1
+
2
2
7
2
7
R
2
.
.
.
.
.
.
+
2
R
2
7
2
8
+
R
1
7
2
9
+
2
R
1
7
3
0
.
.
.
.
subtracing 2 equations,
2
1
7
2
9
S
−
(
2
1
7
2
9
−
1
)
S
=
R
1
7
2
9
+
(
R
1
+
R
2
+
R
3
.
.
.
.
.
.
+
R
1
7
2
8
)
S
=
R
1
7
2
9
+
R
1
7
3
0
−
R
1
7
2
9
=
R
1
7
3
0
=
F
1
7
3
0
(
1
7
2
9
)
note this
we can say that
F
k
n
=
⎩
⎪
⎨
⎪
⎧
1
,
2
k
−
2
,
∑
x
=
1
n
(
F
k
−
x
n
)
,
k
=
1
1
<
k
≤
n
+
1
k
≥
n
+
1
hence,
F
1
7
3
0
1
7
2
9
=
2
1
7
3
0
−
2
=
2
1
7
2
8
and
l
o
g
2
(
2
1
7
2
8
)
=
1
7
2
8
Did the same! Well, you are quite good, really at 13!
Problem Loading...
Note Loading...
Set Loading...
The key is generating functions . For any Fibonacci n -step sequence { F k ( n ) } k = 0 ∞ , the generating function is
g ( x , n ) = 1 − x − x 2 − … − x n x = k = 1 ∑ ∞ F k ( n ) x k ( ∗ )
Observe that we can rewrite g ( x , n ) as
2 − x − 1 x n + 1 − 1 x = x n + 1 − 2 x + 1 x ( 1 − x )
Substituting in x = 2 1 gives
g ( 2 1 , n ) = ( 2 1 ) n + 1 − 2 ( 2 1 ) + 1 2 1 ( 1 − 2 1 ) = ( 2 1 ) n + 1 4 1 = 2 n − 1
Since our n = 1 7 2 9 , our sum is then
k = 1 ∑ ∞ 2 k F k ( 1 7 2 9 ) = g ( 2 1 , 1 7 2 9 ) = 2 1 7 2 8
Thus,
lo g 2 ( k = 1 ∑ ∞ 2 k F k ( 1 7 2 9 ) ) = lo g 2 ( 2 1 7 2 8 ) = 1 7 2 8