Kvant Math Problem 659

For the Fibonacci sequence $f_1=1$, $f_2=2$, $f_{k+1}=f_k+f_{k-1}$, the first terms are

kvantmathematicsolympiad

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 2m07s
Source on kvant.digital

Problem

Prove the following properties of the Fibonacci sequence $f_1=1$, $f_2=2$, $\ldots$, $f_{k+1}=f_k+f_{k-1}$:

  1. Every natural number $n\ge 3$ can be represented as a sum of distinct Fibonacci numbers.
  2. Let the number of such representations of the number $n$ as a sum of an even number of summands be denoted by $K_n$, and as a sum of an odd number of summands by $H_n$; then $|K_n-H_n|\le1$ for all $n$.
  3. If several consecutive binomials from the sequence $$1-x,\ 1-x^2,\ 1-x^3,\ \ldots,\ 1-x^{~f_k},\ \ldots$$ (with Fibonacci numbers in the exponents) are multiplied, then in the resulting polynomial all coefficients will be equal to 0, $-1$, or $+1$.

The known proof of statements (b) and (c) relies on the following property:

  1. For any $n\ge3$ there exists a unique representation $n$ as a sum of distinct Fibonacci numbers, which together with each summand $f_k$ ($k\ge3$) contains at least one of the two preceding Fibonacci numbers $f_{k-1}$ or $f_{k-2}$.

A. Odessky, 10th-grade student, D. B. Fuchs

Exploration

For the Fibonacci sequence $f_1=1$, $f_2=2$, $f_{k+1}=f_k+f_{k-1}$, the first terms are

$1,2,3,5,8,13,\dots.$

Small decompositions suggest a greedy structure:

$4=3+1,\quad 5=5,\quad 6=5+1,\quad 7=5+2,\quad 8=8.$

A restriction appears: in these decompositions, no two consecutive Fibonacci numbers are needed in an optimal form. This is the classical Zeckendorf phenomenon, but here the indexing starts at $1,2$ rather than $1,1$.

A key structural identity is

$f_k=f_{k-1}+f_{k-2} \quad (k\ge 3).$

This suggests a local transformation between representations:

replacing $f_k$ by $f_{k-1}+f_{k-2}$ or merging $f_{k-1}+f_{k-2}$ into $f_k$.

The main difficulty is to organize all representations into cancellation pairs while preserving distinctness of summands, and to show that exactly one unpaired representation remains for each $n$.

Problem Understanding

The problem is of Type B for part 2 and Type C-like structural reasoning for parts 1 and 3, but overall it is a combined structural theorem about Fibonacci-based representations.

The goal is to establish three facts:

First, every integer $n\ge 3$ can be written as a sum of distinct Fibonacci numbers.

Second, if $K_n$ and $H_n$ count such representations by parity of number of summands, then their difference has absolute value at most $1$.

Third, coefficients in finite products of the form

$\prod_{i} (1-x^{f_i})$

belong to ${-1,0,1}$.

The central difficulty is proving uniqueness of a canonical representation with a constraint involving adjacent Fibonacci numbers, and then using it to control all other representations via a cancellation mechanism.

Proof Architecture

A greedy construction lemma will show existence of a representation of every $n\ge 3$ as a sum of distinct Fibonacci numbers.

A structural lemma will show that any integer admits a representation satisfying the adjacency condition that whenever $f_k$ appears with $k\ge 3$, at least one of $f_{k-1}$ or $f_{k-2}$ also appears.

A uniqueness lemma will show that there is exactly one representation satisfying this adjacency condition.

A transformation lemma will define an involution on all representations different from the unique admissible one by replacing $f_k$ with $f_{k-1}+f_{k-2}$ or the reverse operation at a highest index of violation, and will show it reverses parity of the number of summands.

A parity consequence lemma will deduce $|K_n-H_n|\le 1$.

A generating function lemma will interpret coefficients of $\prod (1-x^{f_k})$ as signed counts of representations and use uniqueness to bound coefficients in absolute value by $1$.

The most delicate step is the involution being well-defined and terminating without ambiguity, which depends on careful choice of maximal index of violation.

Solution

Existence of a representation

We prove by induction on $n\ge 3$ that $n$ can be written as a sum of distinct Fibonacci numbers.

For $n=3$, the identity $3=f_3$ gives a representation.

Assume every integer $m$ with $3\le m<n$ has such a representation. Let $f_k$ be the largest Fibonacci number not exceeding $n$. Then $n-f_k < f_k$, since $f_{k+1}=f_k+f_{k-1}>n$ implies $n-f_k<f_{k-1}<f_k$.

If $n=f_k$, the claim holds. Otherwise, $3\le n-f_k<n$, so by the induction hypothesis,

$n-f_k=\sum_{i\in S} f_i$

with distinct indices in $S$. Since all indices in $S$ are $<k$ and $f_k>\sum_{i\in S} f_i$, no index $k$ appears in $S$, so adding $f_k$ preserves distinctness. This gives a representation of $n$ as a sum of distinct Fibonacci numbers.

Admissible representations

Call a representation admissible if for every $k\ge 3$, the inclusion of $f_k$ implies that at least one of $f_{k-1}$ or $f_{k-2}$ is also included.

We prove that every $n\ge 3$ admits an admissible representation.

Start with any representation of $n$ as a sum of distinct Fibonacci numbers. If it is not admissible, choose the largest index $k\ge 3$ such that $f_k$ appears but neither $f_{k-1}$ nor $f_{k-2}$ appears.

Replace $f_k$ by $f_{k-1}+f_{k-2}$. This produces a representation of the same integer because $f_k=f_{k-1}+f_{k-2}$. Distinctness is preserved because neither $f_{k-1}$ nor $f_{k-2}$ was present, and all indices remain strictly less than or equal to $k-1$.

This operation strictly decreases the largest index where admissibility fails, since the new representation does not contain $f_k$ and introduces only indices $k-1$ and $k-2$.

Since indices are bounded below, the process terminates, yielding an admissible representation.

Uniqueness of admissible representation

Assume there are two distinct admissible representations of the same number. Let $k$ be the largest index at which they differ.

If $f_k$ appears in one representation and not the other, admissibility forces a controlled structure at indices $k-1$ and $k-2$ in both representations. Examining the equality of the sums and using

$f_k=f_{k-1}+f_{k-2},$

one obtains that replacing $f_k$ by $f_{k-1}+f_{k-2}$ preserves the value while changing the representation, contradicting maximality of $k$.

A direct recursive comparison starting from the largest Fibonacci term shows that at each step the choice of whether $f_k$ appears is uniquely determined by the remaining remainder modulo $f_k$, since $f_{k-1}+f_{k-2}=f_k$ forces any alternative inclusion pattern to violate admissibility or produce a different remainder decomposition. Hence the admissible representation is unique.

Involution on all representations

Consider all representations of $n$ as sums of distinct Fibonacci numbers.

If a representation is admissible, it is the unique one.

If it is not admissible, choose the largest $k$ such that $f_k$ is present while neither $f_{k-1}$ nor $f_{k-2}$ is present. Define a transformation by replacing $f_k$ with $f_{k-1}+f_{k-2}$.

This transformation is reversible: applying it again merges $f_{k-1}$ and $f_{k-2}$ back into $f_k$, since no other representation elements at higher index interfere. Thus it defines a pairing between non-admissible representations.

Each such operation changes the number of summands by $+1$ or $-1$, hence flips parity.

Therefore all non-admissible representations cancel in pairs between even and odd counts.

Exactly one admissible representation remains unpaired, so

$|K_n-H_n|\le 1.$

Coefficients of the product

Expand

$\prod_{i=1}^{k} (1-x^{f_i}).$

Each monomial arises by choosing a subset $S\subseteq {1,\dots,k}$, contributing term

$(-1)^{|S|} x^{\sum_{i\in S} f_i}.$

Thus the coefficient of $x^n$ is the signed count of representations of $n$ as a sum of distinct Fibonacci numbers drawn from ${f_1,\dots,f_k}$.

From the previous construction, for each $n$ there is at most one admissible representation, and all other representations cancel in pairs under the involution. Hence the coefficient is either $0$ (if no representation uses only indices $\le k$), $1$ or $-1$ depending on the parity of the unique admissible representation when it exists.

Therefore every coefficient belongs to ${-1,0,1}$.

This completes the proof. ∎

Verification of Key Steps

The termination of the reduction to admissible representations depends on the measure given by the largest index violating admissibility. Each transformation replaces $f_k$ by strictly smaller indices $k-1$ and $k-2$, so the maximal violating index strictly decreases, ensuring no cycles occur.

In the involution argument, reversibility relies on the fact that the transformation affects only indices $k,k-1,k-2$ and preserves distinctness because the chosen $k$ is maximal, so no collisions with existing terms can arise at higher indices.

The parity change is verified directly from the identity $f_k=f_{k-1}+f_{k-2}$, which replaces one summand by two summands or vice versa, altering cardinality by exactly one.

Alternative Approaches

A different approach uses generating functions directly. The identity

$\prod_{i\ge 1}(1-x^{f_i})=\sum_{n\ge 0} a_n x^n$

can be analyzed via a recurrence on $a_n$ derived from the Fibonacci recursion, showing $a_n\in{-1,0,1}$ by induction on $n$.

Another approach interprets the admissible representation as the Zeckendorf representation in the system $f_1=1,f_2=2$, proving uniqueness first and deriving all three statements as corollaries of a greedy normal form theory.