Prove by Induction on k. using Fibonacci Numbers

Question

$$F_{k-2}+F_{k-4}+...+F_{k\,mod\,2+2}=F_{k-1}-1, \quad \quad if\: k\geq2.$$

This equation is to prove by induction on $k;$ the left-hand side is zero when $k$ is $2$ or $3$. Therefore $k_{1}$ is the greedily chosen value described earlier, and the representation must be unique.

Here is my Attempt.

I have attempted to solve this problem using induction, Please if anyone confirms that my attempt is true for induction step. Or If someone helps me with this answer if anything goes wrong.

$$F_{k-2}+F_{k-4}+...+F_{k\,mod\,2+2}=F_{k-1}-1 \quad \quad if\,k\geq2$$

My Attempt: Base case $k=2$ $$F_{2-2}+F_{2-4}+...+F_{2\,mod \,2+2}=F_{2-1}-1$$ As $2\, mod\,2=0$ therefore, $$F_{0}+F_{-2}+...+F_{0+2}=F_{1}-1$$ $$F_{0}+F_{-2}+...+F_{2}=F_{1}-1$$ As $F_{0}=0,\,F_{-2}=-1,\,F_{2}=1,\,and\,F_{1}=1\,$therefore, $$0+(-1)+...+1=1-1$$ $$0-1+...+1=1-1$$ $$0=0 \\ which\,\,is\,\,true\,\,the\,\,left\,\,hand\,\,side\,\,is\,\,zero\,\,when\,\,k\,\,is\,\,2.$$ Now the Induction Step: $k=k+1$ on left hand side $$F_{k+1-2}+F_{k+1-4}+...+F_{k+1\,mod\,2+2}$$ $$F_{k-1}+F_{k-3}+...+F_{k+1\,mod\,2+2}$$ As we know that $F_{k-1}=F_{k+1}+F_{k}$ and $F_{k-3}=2F_{k+1}-3F_{k}$ therefore, $$F_{k+1}+F_{k}+2F_{k+1}-3F_{k}+...+F_{k+1\,mod\,2+2}$$ $$(F_{k+1}+2F_{k+1})+(F_{k}-3F_{k})+...+F_{k+1\,mod\,2+2}$$ $$(3F_{k+1})+(-2F_{k})+...+F_{k+1\,mod\,2+2}$$ $$3F_{k+1}-2F_{k}+...+F_{k+1\,mod\,2+2}$$

Answer 1

The question can be rewritten as $$ F_{n-1}-1=\sum_{k=1}^{\left\lfloor\frac{n-2}2\right\rfloor}F_{2k+(n\bmod2)}\tag1 $$ For $n=2$ or $n=3$, the sum on the right side of $(1)$ is an empty sum and the left hand side of $(1)$ is $0$. For these two cases, $(1)$ holds.

Suppose that $(1)$ holds. Adding $F_n$ to both sides gives $$ F_{n+1}-1=\sum_{k=1}^{\left\lfloor\frac{n}2\right\rfloor}F_{2k+(n\bmod2)}\tag2 $$ the left side follows by the recurrence $F_{n+1}=F_n+F_{n-1}$ and the right side follows because $F_{2\left\lfloor\frac{n}2\right\rfloor+(n\bmod2)}=F_n$ for both $n$ even and $n$ odd. Since $(2)$ is $(1)$ for $n\mapsto n+2$, $(1)$ follows for all $n\ge2$, even and odd.

---

We can combine the parallel inductions above as a single induction. Break $(1)$ into $P(m)$: $$ \begin{align} F_{2m-1}-1&=\sum_{k=1}^{m-1}F_{2k}\tag3\\ F_{2m}-1&=\sum_{k=1}^{m-1}F_{2k+1}\tag4 \end{align} $$ $P(1)$ is simply $$ \begin{align} \overbrace{F_1-1\vphantom{\sum_{k=1}^0}}^0&=\overbrace{\sum_{k=1}^0F_{2k}}^0\tag5\\ F_2-1&=\sum_{k=1}^0F_{2k+1}\tag6 \end{align} $$ Now suppose that $P(m)$ is true. Add $F_{2m}$ to both sides of $(3)$ and $F_{2m+1}$ to both sides of $(4)$. We get $$ \begin{align} F_{2m+1}-1&=\sum_{k=1}^{m}F_{2k}\tag7\\ F_{2m+2}-1&=\sum_{k=1}^{m}F_{2k+1}\tag8 \end{align} $$ which is $P(m+1)$.

This completes the induction.

Answer 2

I have attempted to solve this problem using induction, Please if anyone confirms that my attempt is true for induction step. Or If someone helps me with this answer if anything goes wrong.

$$F_{k-2}+F_{k-4}+...+F_{k\,mod\,2+2}=F_{k-1}-1 \quad \quad if\,k\geq2$$

My Attempt: Base case $k=2$ $$F_{2-2}+F_{2-4}+...+F_{2\,mod \,2+2}=F_{2-1}-1$$ As $2\, mod\,2=0$ therefore, $$F_{0}+F_{-2}+...+F_{0+2}=F_{1}-1$$ $$F_{0}+F_{-2}+...+F_{2}=F_{1}-1$$ As $F_{0}=0,\,F_{-2}=-1,\,F_{2}=1,\,and\,F_{1}=1\,$therefore, $$0+(-1)+...+1=1-1$$ $$0-1+...+1=1-1$$ $$0=0 \\ which\,\,is\,\,true\,\,the\,\,left\,\,hand\,\,side\,\,is\,\,zero\,\,when\,\,k\,\,is\,\,2.$$ Now the Induction Step: $k=k+1$ on left hand side $$F_{k+1-2}+F_{k+1-4}+...+F_{k+1\,mod\,2+2}$$ $$F_{k-1}+F_{k-3}+...+F_{k+1\,mod\,2+2}$$ As we know that $F_{k-1}=F_{k+1}+F_{k}$ and $F_{k-3}=2F_{k+1}-3F_{k}$ therefore, $$F_{k+1}+F_{k}+2F_{k+1}-3F_{k}+...+F_{k+1\,mod\,2+2}$$ $$(F_{k+1}+2F_{k+1})+(F_{k}-3F_{k})+...+F_{k+1\,mod\,2+2}$$ $$(3F_{k+1})+(-2F_{k})+...+F_{k+1\,mod\,2+2}$$ $$3F_{k+1}-2F_{k}+...+F_{k+1\,mod\,2+2}$$

Answer 3

So, we agree on understanding the meaning of the dots
" ... $F_{k-2}+F_{k-4}+F_{k-6}+F_{k-8}+\cdots$ and so on till $F_{k\,mod\,2+2}$".

Now we shall agree on the meaning of "till".

Using the dots leads to assume (as a standard interpretation) that you mean to say $$ F_{\,k - 2} + F_{\,k - 4} + \cdots + F_{\,k\bmod 2 + 2} \quad \Rightarrow \quad \sum\limits_{1\, \le \,j\, \le \,\left\lfloor {{k \over 2}} \right\rfloor - 1} {F_{\,k - 2j} } $$ and the standard interpretation of this sum is that, whenever the index does not respect the conditions imposed, then the sum is considered null, e.g. $$ \sum\limits_{a\, \le \,k\, \le \,b} {f(k)} \quad \Rightarrow \quad \sum\limits_{a\, \le \,k\, \le \,b\quad \left| {\;b\, < \,a} \right.} {f(k)} = \sum\limits_{k\, \in \;\emptyset } {f(k)} = 0 $$

There is another interpretation of the sum allowing for the bounds to be reversed, but you do not use dots to indicate it.

Coming to your problem, since $$ \eqalign{ & k - 2j = k\bmod 2 + 2\quad \Rightarrow \quad \cr & \Rightarrow \quad 2j = k - k\bmod 2 - 2 = 2\left\lfloor {{k \over 2}} \right\rfloor + k\bmod 2 - k\bmod 2 - 2 \cr & \Rightarrow \quad j = \left\lfloor {{k \over 2}} \right\rfloor - 1 \cr} $$ Then we write your recurrence as $$ \bbox[lightyellow] { F_{\,k - 1} - 1 = \sum\limits_{1\, \le \,j\, \le \,\left\lfloor {{k \over 2}} \right\rfloor - 1} {F_{\,k - 2j} } \quad \left| {\;2 \le k} \right. } \tag{1}$$ and, it seems that, the thesis you want to demonstrate is :

if the $F_k$ obeys the Fibonacci recurrence $F_{k+1}=F_{k}+F_{k-1} \quad | \; 2 \le k$ then they obey to the recurrence above.

The starting conditions are $$ \eqalign{ & k = 2\quad \Rightarrow \quad F_{\,1} - 1 = \sum\limits_{1\, \le \,j\, \le \,0} {F_{\,2 - 2j} } = 0\quad \Rightarrow \quad F_{\,1} = 1 \cr & k = 3\quad \Rightarrow \quad F_{\,2} - 1 = \sum\limits_{1\, \le \,j\, \le \,0} {F_{\,3 - 2j} } = 0\quad \Rightarrow \quad F_{\,2} = 1 \cr} $$ which indicates that actually $F_1 \; F_2$ equal the respective Fibonacci N.. But let's proceed apart from initial conditions because in the thesis we did not involve the initial conditions, but only the recurrence.

We can put $$ k = 2m + i\quad \left| \matrix{ \;1 \le m \hfill \cr \;i = 0,1 \hfill \cr} \right. $$ and write the system $$ \bbox[lightyellow] { \left\{ \matrix{ F_{\,2m - 1} - 1 = \sum\limits_{1\, \le \,j\, \le \,m - 1} {F_{\,2\left( {m - j} \right)} } \hfill \cr F_{\,2m} - 1 = \sum\limits_{1\, \le \,j\, \le \,m - 1} {F_{\,2\left( {m - j} \right) + 1} } \hfill \cr} \right.\quad \Leftrightarrow \quad \left\{ \matrix{ F_{\,2m} + F_{\,2m - 1} - 2 = \sum\limits_{1\, \le \,j\, \le \,m - 1} {\left( {F_{\,2\left( {m - j} \right)} + F_{\,2\left( {m - j} \right) + 1} } \right)} \hfill \cr F_{\,2m} - F_{\,2m - 1} = \sum\limits_{1\, \le \,j\, \le \,m - 1} {\left( {F_{\,2\left( {m - j} \right) + 1} - F_{\,2\left( {m - j} \right)} } \right)} \hfill \cr} \right. } \tag{2}$$ since the validity of a system implies the validity of the system of the sum and difference of the single lines.

So if the $F$ obeys the Fibonacci recurrence, then the first reads $$ \bbox[lightyellow] { \eqalign{ & F_{\,2m} + F_{\,2m - 1} - 2 = F_{\,2m + 1} - 2 = F_{\,2\left( {m + 1} \right) - 1} - 2 = \cr & = \sum\limits_{1\, \le \,j\, \le \,m - 1} {\left( {F_{\,2\left( {m - j} \right)} + F_{\,2\left( {m - j} \right) + 1} } \right)} = \sum\limits_{1\, \le \,j\, \le \,m - 1} {F_{\,2\left( {m - j} \right) + 2} } = \cr & = \sum\limits_{1\, \le \,j\, \le \,m - 1} {F_{\,2\left( {m + 1} \right) - 2j} } = \sum\limits_{1\, \le \,j\, \le \,m + 1 - 2} {F_{\,2\left( {m + 1} \right) - 2j} } = \cr & = \sum\limits_{\,1\, \le \,j\, \le \,\left\lfloor {{{2\left( {m + 1} \right)} \over 2}} \right\rfloor - 1 - 1} {F_{\,2\left( {m + 1} \right) - 2j} } = \sum\limits_{\,1\, \le \,j\, \le \,\left\lfloor {{{2\left( {m + 1} \right)} \over 2}} \right\rfloor - 1} {F_{\,2\left( {m + 1} \right) - 2j} } - F_{\,2\left( {m + 1} \right) - 2\left( {\left\lfloor {{{2\left( {m + 1} \right)} \over 2}} \right\rfloor - 1} \right)} = \cr & = \sum\limits_{\,1\, \le \,j\, \le \,\left\lfloor {{k \over 2}} \right\rfloor - 1} {F_{\,2\left( {m + 1} \right) - 2j} } - F_{\,2} \quad \Rightarrow \cr & \Rightarrow \quad F_{\,2\left( {m + 1} \right) - 1} - 2 = \sum\limits_{\,1\, \le \,j\, \le \,\left\lfloor {{k \over 2}} \right\rfloor - 1} {F_{\,2\left( {m + 1} \right) - 2j} } - F_{\,2} = \sum\limits_{\,1\, \le \,j\, \le \,\left\lfloor {{k \over 2}} \right\rfloor - 1} {F_{\,2\left( {m + 1} \right) - 2j} } - 1\quad TRUE \cr} } \tag{3.a}$$ while the second line reads $$ \bbox[lightyellow] { \eqalign{ & F_{\,2m} - F_{\,2m - 1} = F_{\,2m - 2} = \sum\limits_{1\, \le \,j\, \le \,m - 1} {\left( {F_{\,2\left( {m - j} \right) + 1} - F_{\,2\left( {m - j} \right)} } \right)} = \cr & = \sum\limits_{1\, \le \,j\, \le \,m - 1} {\left( {F_{\,2m - 1 - 2j} } \right)} = \sum\limits_{1\, \le \,j\, \le \,\left\lfloor {{{2m - 1} \over 2}} \right\rfloor - 1} {\left( {F_{\,2m - 1 - 2j} } \right)} \quad TRUE \cr} } \tag{3.b}$$

----- Answer to your comment -----

If you want to restate the above in a "classical" induction process, then you can put

1) Thesis $$ {\rm Fibonacci}\;{\rm Rec}{\rm .}\quad \Leftrightarrow \quad \left( 1 \right) $$

2) Initial Match

Since the recurrence is of degree two (it involves $\Delta _{\,k} ^{\,2} F_{\,k} $) then you need to fix two initial conditions, and we saw that $$ {\rm Thesis}\;{\rm TRUE}\quad \left| {\;k = 2,3} \right. $$

3) True for $k=2m-1,2m$ implies true for $k=2m,2m+1$

$$ \left\{ {\matrix{ {F_{\,2m - 1} - 1 = \sum\limits_{1\, \le \,j\, \le \,m - 1} {F_{\,2\left( {m - j} \right)} } } & \Leftrightarrow & {F_{\,2m} - 1 = \sum\limits_{1\, \le \,j\, \le \,m - 1} {F_{\,2\left( {m - j} \right) + 1} } } \cr {F_{\,2m} - 1 = \sum\limits_{1\, \le \,j\, \le \,m - 1} {F_{\,2\left( {m - j} \right) + 1} } } & \Leftrightarrow & {F_{\,2m + 1} - 1 = \sum\limits_{1\, \le \,j\, \le \,m} {F_{\,2\left( {m - j} \right) + 2} } } \cr } } \right. $$ i.e. $$ \left\{ {\matrix{ {F_{\,2m - 1} - 1 = \sum\limits_{1\, \le \,j\, \le \,m - 1} {F_{\,2\left( {m - j} \right)} } } & \Leftrightarrow & {F_{\,2m} - 1 = \sum\limits_{1\, \le \,j\, \le \,m - 1} {F_{\,2\left( {m - j} \right) + 1} } } \cr {F_{\,2m} - 1 = \sum\limits_{1\, \le \,j\, \le \,m - 1} {F_{\,2\left( {m - j} \right) + 1} } } & \Leftrightarrow & {F_{\,2m - 1} - 1 = \sum\limits_{1\, \le \,j\, \le \,m - 1} {F_{\,2\left( {m - j} \right)} } } \cr } } \right. $$ and thus $$ {\rm Thesis}\;{\rm TRUE}\quad \left| {\;k = 2,3} \right.\quad \Leftrightarrow \quad {\rm Thesis}\;{\rm TRUE}\quad \left| {\;k = 2m,2m + 1\quad \left| {\;1 \le m} \right.} \right. $$