Base Cases in proving Zeckendorf's Theorem by Strong Induction $\forall n \in N:\exists\ \text{Fibonacci numbers}\ F_{i_1},\ldots,F_{i_k} $
such that:
$ \sum F_{i_k}=n$
Note:
Every Fibonacci number can appear only once
If $n$ is not a Fibonacci number, and $F_k$ is the largest Fibonacci number less than $n$, look at $n-F_k$.
What bases should we prove to be sure that strong induction is satisfied?
 A: We present a general proof that covers the Fibonacci numbers.
Theorem: Suppose that $x_n$ is the positive integer sequence numbers with conditions $x_1=1$ and
$$\forall n=1,2,\cdots  \quad , \quad x_{n+1}\leq 1+\sum_{i=1}^n\,x_i$$
Now, if $0<m<1+\sum_{i=1}^k x_i$, then there is a sub-sequence like $I$ from $\{1,2,\cdots,k\}$, such that
$$m=\sum_{i\in I}\,x_i$$
Proof: The theorem is true for $k=1$. Consider the theorem holds
for $k\leq N$. Now, we prove that if $0<m<1+\sum_{i=1}^{N+1} x_i$, then there is a sub-sequence like $J$ from $\{1,2,\cdots,N+1\}$, such that $m=\sum_{j\in J}x_j$.
If $m<1+\sum_{i=1}^{N} x_i$, then by the weak condition, theorem is true. So, suppose that
the value of $m$ holds in the following relation
$$
1+\sum_{i=1}^{N} x_i \leq m \leq 1+\sum_{i=1}^{N+1} x_i
$$
that results that
$$
m-x_{N+1}\geq 1+\sum_{i=1}^{N} x_i-x_{N+1}\geq 0
$$
If $m-x_{N+1}=0$ then the result is obtained but in the case $m-x_{N+1}\neq 0$, we get
$$0<m-x_{N+1}< 1+\sum_{i=1}^{N} x_i$$
that results that there is a sub-sequence like $I$ from $\{1,2,\cdots, N\}$, in the following form
$$
m-x_{N+1}=\sum_{i\in I}x_i \quad \Rightarrow 
\quad J=I \cup \{N+1\}
$$
which completes the proof.
