Prove by induction that Fn denotes the Fibonacci sequence. $$F_n=\sum_{j=0}^k {n-j \choose j} \text{ where k=}\left\lfloor\frac n2\right\rfloor$$
$\lfloor\cdot\rfloor$ denotes floor or Greatest Integer Function
Here's what I've done so far but I seem to be getting nowhere:
Base Case:
Even: test for n=0
k = 0 F0 = Sum(j=0,0) (n-j,j) F0 = (1,0) = 1
Odd: test for n=1
k = 0
F1 = Sum(j=0,0) (n-j,j) F1 = (1,0) = 1
These are the first two numbers in the fibonacci sequence so this holds true.
Induction:
Assume true for n=a, test for n=a+1
Even:
ka+1 = (a+1)/2
a must therefore be odd and so:
ka = (a-1)/2
Fa+1 = Sum(j=0,(a+1)/2) (a+1-j,j)
Fa+1 = Fa + (a+1-(a+1)/2,(a+1)/2)
Fa+1 = Fa + ((a+1)/2,(a+1)/2)
Fa+1 = Fa + ((a+1)/2)! / ((a+1)/2)!(0)!
Fa+1 = Fa + 1
???
Odd:
k = a/2
Fa+1 = Sum(j=0,a/2) (a+1-j,j)
Fa+1 = Fa + (a+1-a/2,a/2)
Fa+1 = Fa + (a+2/2,a/2)
Fa+1 = Fa + (a+2/2)! / (a/2)!((a+2/2)-(a/2))!
Fa+1 = Fa + (a+2/2)! / (a/2)!
Fa+1 = Fa + (a/2)!(a+1/2)(a+2/2) / (a/2)!
Fa+1 = Fa + (a+1/2)(a+2/2)
???
For $\;n=1\;$ :
$$\sum_{j=0}^{\left\lfloor\frac12\right\rfloor=0}\binom{1-j}j=\binom10=1=F_1\;\;\color{green}\checkmark$$
Assume for all integers up to$\;n-1\;$ .
First case: $\;n\;$ is even, so $\;n=2m\implies\left\lfloor\frac n2\right\rfloor=m\;$ , and thus
$$\sum_{j=0}^{\left\lfloor\frac n2\right\rfloor=m}\binom{n-j}j=\sum_{j=0}^{m-1}\binom{n-j}j+\binom{n-m}m\stackrel{\color{red}{(**)}}=$$
$$=\sum_{j=0}^{\lfloor \frac{n-2}2\rfloor}\binom{n-j}j+\sum_{j=0}^{\lfloor\frac{n-1}2\rfloor}\binom{n-j}j\stackrel{\text{Ind. Hyp.}}=F_{2m-2}+F_{2m-1}=:F_{2m}=F_n$$
$\;\color{red}{(**)}\;\;$ Because the sum to $\;m-1\;$ is obtained with both
$$\;\lfloor \frac{n-2}2\rfloor=\lfloor\frac{2m-2}2\rfloor=\lfloor m-1\rfloor=m-1\;$$
and
$$\;\lfloor \frac{n-1}2\rfloor=\lfloor\frac{2m-1}2\rfloor=\left\lfloor m-\frac12\right\rfloor=m-1\;\;...!$$
Now you do the other case.