Prove $S(n) = S(f_{k}) + S(n-f_{k}) + n-f_{k}$

27 Views Asked by Bumbble Comm At 30 Mar 2026 - 5:30

Problem:

Lets $Z(n)$ be the number of numbers of in Zeckendorf Representation of $n$

and Let

$ S(n) = \sum_{1}^n Z(i) $ and $f_{k}= k_{th}$ fibonacci number not greater than $n$

Prove $S(n) = S(f_{k}) + S(n-f_{k}) + n-f_{k}$

My thoughts:

Z(i) is https://oeis.org/A007895

Intuitively I can see the equation holds when n=f(k) form.

Trying $n=f_{k}+1$ form We get,

$Z(n) = Z(1) + 1$, is it true?

If we remove 1 from n we get $f_k$ and $Z(f_k)$ is always $1$. So this can be explained by $Z(n) = Z(1) + Z(f_k)$ where $Z(1)$ is due to the removed 1.
Now lets Try $n=f_{k}+2$ form, we get,

$Z(n) + Z(n-1) = Z(1) + Z(2) + 2$, is it true?

If we remove 2 from n we get $f_k$ and $Z(f_k)$ is always $1$. So this can be explained by $Z(n) + Z(n-1) = (Z(1) + Z(f_k)) + (Z(2) + Z(f_k))$ where $Z(1)$ is due to the removed 1.
If we Try $n=f_{k}+u$ form, we get $S(f_{k}+u) = S(f_{k}) + S(u) + u$

So in other words we are to prove sum of immediate $u$ next $Z(i)s$ after $f_k$ is $u$ more than the first $u$ $Z(i)s$

There are 1 best solutions below

Bumbble Comm On 06 Feb 2023 - 7:30

Let $n = f_k + u$

Imagine we are removing $u$ as a chunk and land on $f_k$

Now both $Z(u)$ and $Z(f_k)$ are guaranteed to exist and also guaranteed to be unique by Zeckendorf's lemma. So we can write,

$Z(f_k + u) = Z(f_k) + Z(u)$

We know Z(f_k)=1,

$Z(f_k + u) = 1 + Z(u)$

Now if we do Sum for all $i$ from $1$ to $u$

Now summing,

$S(n) - S(f_k) = u + S(u)$

$\implies S(n) = S(f_k) + S(u) + u$

$\implies S(n) = S(f_k) + S(n - f_k) + n - f_k$