Exercise 4.4.4 ($F_{n+1} = \sum\limits_{i = 0}^{\lfloor n/2 \rfloor} \binom{n-i}{i}$)

Question

Prove that for $n \geq 2$,
$$F_n = \binom{n-1}{0} + \binom{n-2}{1} + \binom{n-3}{2} + \binom{n-4}{3} + \cdots + \binom{n-j}{j-1}$$
where the sum of the binomial coefficients on the right terminates with the largest $j$ so that $2 j\leq n+1$.

\bigskip
Hint. Recall (1.15)
$$
\frac{1}{(1-z)^{\alpha + 1}}= \sum_{k=0}^\infty \binom{\alpha + k}{k} z^k.
$$

Richard Ganaye · Accepted Answer

ewcommand{\N}{\mathbb{N}} I don't understand the hint, but I give three very different proofs of this formula. (If somebody gives an alternative solution by following the hint, I am interested.) Note that the sentence is equivalent to \begin{align*} F_{n+1} &= \binom{n}{0} + \binom{n-1}{1} + \binom{n-2}{2} + \binom{n-3}{3} + \cdots + \binom{n-j}{j} \qquad (n \geq 1) \end{align*} where the sum of the binomial coefficients on the right terminates with the largest $j$ so that $2 j\leq n$, that is $j = \lfloor n / 2 floor$. Thus this formula may be written \begin{align} F_{n+1} = \sum_{i = 0}^{\lfloor n/2 floor} \binom{n-i}{i}. \end{align} Recall that by definition $\binom{n}{p} = 0$ if $p>n$. Therefore (1) is equivalent to $F_{n+1} = \sum\limits_{i = 0}^{n} \binom{n-i}{i}$. \bigskip {\bf First proof.} (by generatrix functions) \begin{proof} Put $$\lambda = \frac{1-\sqrt{5}}{2}, \qquad \mu = \frac{1 + \sqrt{5}}{2},$$ so that by (4.6) $$F_n = \frac{\mu^n - \lambda^n}{\mu - \lambda}.$$ Consider the power series \begin{align} f(x) = \sum_{k = 0}^\infty F_k x^k. \end{align} We note that \begin{align*} \frac{F_{k+1}}{F_{k}} &=\frac{\mu^{k+1} - \lambda^{k+1}}{\mu^k - \lambda^k}\ &= \mu \, \frac{1-\left(\frac{ \lambda}{\mu} ight)^{k+1}}{1-\left(\frac{ \lambda}{\mu} ight)^{k}}. \end{align*} Since $\left | \frac{\lambda}{\mu} ight | < 1$, we obtain $\lim_{k o \infty} (\lambda/\mu)^{k} = 0$, so $$\lim_{k o \infty} \frac{F_{k+1}}{F_{k}} = \mu.$$ Therefore, for all real $x e 0$, $$\lim_{k o \infty} \left | \frac{F_{k+1} x^{k+1}}{F_k x^k} ight | = \mu |x|.$$ By the d'Alembert's ratio test, the series (1) converges for $ |x| < 1/\mu$, and diverges for $|x| >1/\mu$: the radius of convergence of the power series (1) is $$R = \frac{1}{\mu} = \frac{\sqrt{5} - 1}{2}.$$ Suppose that $|x| < 1/\mu$. Then the series $$\sum_{k = 0}^\infty F_k x^k,\qquad \sum_{k = 0}^\infty \mu^k x^k, \qquad \sum_{k = 0}^\infty \lambda^k x^k$$ are convergent. Therefore \begin{align*} f(x) &= \sum_{k = 0}^\infty F_k x^k\ &= \frac{1}{\mu - \lambda} \left ( \sum_{k = 0}^\infty \mu^k x^k - \sum_{k = 0}^\infty \lambda^k x^k ight)\ &= \frac{1}{\mu - \lambda} \left ( \frac{1}{1 - \mu x } - \frac{1}{1 - \lambda x } ight)\ &= \frac{1}{\mu - \lambda} \, \frac{(\mu - \lambda) x}{(1- \mu x) (1 - \lambda x)}\ &=\frac{x}{1 - x - x^2}. \end{align*} This shows that \begin{align} f(x) = \frac{x}{1 - x - x^2},\qquad (|x] < 1/\mu). \end{align} We can expand $x/(1 - x - x^2)$ in power series, but to avoid problems of convergence and infinite sums, we prefer for simplicity use an asymptotic development in the neighborhood of $0$, at the order $n+1$. First $$f(x) = F_0 + F_1 x + F_2 x^2 + \cdots + F_{n+1} x^{n+1} + o(x^{n+1}).$$ Next, $$\frac{1}{1- u} = 1 + u + u^2 + \cdots + u^{n+1} + o(u^{n+1}) = \sum_{i=0}^{n+1} u^i + o(u^{n+1}).$$ With $u = u(x) = x + x^2 \sim x$, so that $o(u(x)^{n+1}) = o(x^{n+1})$, we obtain \begin{align*} f(x) &= x \, \frac{1}{1 - (x + x^2)}\ &= x \sum_{i = 0}^{n+1}(x + x^2)^i + o(x^{n+1})\ &= x \sum_{i=0}^{n+1} \sum_{j = 0}^i\binom{i}{j} x^{i-j} x^{2j} + o(x^{n+1})\ &= x \sum_{i=0}^{n+1} \sum_{j = 0}^{n+1}\binom{i}{j} x^{i+j} + o(x^{n+1})&( ext{since }\binom{i}{j} = 0 ext{ if } j>i)\ &= x \sum_{k = 0}^{n+1} \sum_{i+j = k} \binom{i}{j} x^k + o(x^{n+1})&( ext{since }x^k = o(x^{n+1}) ext{ if } k > n+1)\ &= \sum_{k = 0}^n x^{k+1} \sum_{i+j = k} \binom{i}{j}\ &= \sum_{k = 0}^n x^{k+1} \sum_{i = 0}^k \binom{k-j}{j}. \end{align*} So $$f(x) = \sum_{k = 0}^{n+1} F_k x^k + o(x^{n+1}) = \sum_{k = 0}^n x^{k+1} \sum_{j = 0}^k \binom{k-j}{j}.$$ By the unicity of the coefficients in these asymptotic expansions, $$F_{n+1} = \sum_{j = 0}^n \binom{n-j}{j}.$$ Since $\binom{n-j}{j} = 0$ if $j >n/2$, $$F_{n+1} = \sum_{j = 0}^{\lfloor n/2 floor} \binom{n-j}{j}\qquad (n\geq 0).$$ So (1) is proven, which is equivalent to the sentence. \end{proof} \bigskip {\bf Second proof} (by induction) Consider the proposition $$\mathscr{P}(n): F_{n+1} = \sum_{j = 0}^n \binom{n-j}{j}.$$ Since $$ \sum_{j = 0}^0 \binom{0-j}{j} = \binom{0}{0} = 1 = F_1,\qquad \sum_{j = 0}^1 \binom{1-j}{j} = \binom{1}{0} + \binom{0}{1} = 0 + 1 = 1 = F_2,$$ $\mathscr{P}(0)$ and $\mathscr{P}(1)$ are true. Now suppose that $\mathscr{P}(n)$ and $\mathscr{P}(n+1)$ are true for some $n \geq 0$. \begin{center} \begin{tabular}{|cccccccccc|} \hline & 1 & 1 & 2 & 3 & 5& $\cdots$ & &$F_{n+1}$&$F_{n+2}$\ \hline 1 & 0 & 0 & 0& 0& & &$\binom{0}{n}$&$\binom{0}{n+1}$&\ 1& 1 & 0 & 0& & & $\iddots$&$\iddots$&&\ 1& 2 & 1 & 0 & & & &&&\ 1& 3 & 3 & 1 & & & &&&\ 1 & & & & & &&&&\ $\vdots$&&&$\iddots$&$\iddots$&&&&&\ &&$\binom{n-2}{2}$&$\binom{n-2}{3}$&&&&&&\ &$\binom{n-1}{1}$&$\binom{n-1}{2}$&&&&&&&\ $\binom{n}{0}$&$\binom{n}{1}$&&&&&&&&\ $\binom{n+1}{0}$&&&&&&&&&\ \hline \end{tabular} \end{center} Then \begin{align*} \left\{ \begin{array}{ll} F_{n+1} &= \sum\limits_{j = 0}^n \binom{n-j}{j},\ F_{n+2} &= \sum\limits_{j = 0}^{n+1} \binom{n+1-j}{j}. \end{array} ight. \end{align*} Then \begin{align*} F_{n+3} &= F_{n+1} + F_{n+2} \ &\sum\limits_{j = 0}^n \binom{n-j}{j} + \sum\limits_{j = 0}^{n+1} \binom{n+1-j}{j}\ &=\sum\limits_{i = 0}^n \binom{n-i}{i} + \sum\limits_{j = 1}^{n+1} \binom{n+1-j}{j} + \binom{n+1}{0}\ & = \sum\limits_{i = 0}^n \binom{n-i}{i} + \sum\limits_{i= 0}^{n} \binom{n-i}{i+1} + 1&(j = i+1).\ \end{align*} By the Pascal's formula (1.14), $$\binom{n-i}{i} + \binom{n-i}{i+1} = \binom{n-i+1}{i+1}.$$ Note that this formula remains true if one of the binomial coefficients is zero, or both are zero. Therefore \begin{align*} F_{n+3} &= \sum\limits_{i = 0}^n \binom{n-i+1}{i+1} + 1\ &= \sum\limits_{j = 1}^{n+1} \binom{n+2 - j}{j} + 1& (j = i+1)\ &= \sum\limits_{j = 0}^{n+1} \binom{n+2 - j}{j}& ( ext{since }\binom{n+2}{0} = 1)\ &= \sum\limits_{j = 0}^{n+2} \binom{n+2 - j}{j}& ( ext{since }\binom{0}{n+2} = 0)\ \end{align*} This shows that $\mathscr{P}(n+2)$ is true, and the induction is done. Therefore $$\forall n \in \N,\ F_{n+1} = \sum\limits_{j = 0}^n \binom{n-j}{j},$$ or removing the null terms, $$\forall n \in \N,\ F_{n+1} = \sum\limits_{j = 0}^{\lfloor n/2 floor} \binom{n-j}{j}.$$ (To obtain the sentence, we replace $n$ by $n-1$.) \bigskip {\bf Third proof} (combinatorial proof) In how many ways can a barrel of $n$ liters be filled with two containers of one liter and two liters, taking into account the order in which these containers are used? For instance, if the barrel is $4$ liters, the solutions are \begin{align*} &1 + 1 + 1 + 1,\ &1 + 1 + 2,\ &1 + 2 + 1,\ &2 + 1 + 1,\ &2+2,\ \end{align*} so that there are $5= F_5$ ways to fill the 4-liter barrel. From a more formal point of view, let us count the number $G_n$ of tuples $(x_1,x_2,\ldots,x_k)$ such that $x_1 + x_2+ \cdots + x_k = n$ and $x_i\in\{1,2\}$ for all $i$. We show that $G_n = F_{n+1}$ by induction for $n\geq 1$. First $G_1 = 1 = F_2$ (there is a unique solution $(1)$), and $G_2 = 2 = F_3$ (two solutions: $(1,1)$ and $(2)$). Suppose now that $G_n = F_{n+1}$ and $G_{n+1} = F_{n+2}$ for some $n \geq 1$. Then we count $G_{n+2}$ considering two cases: if $x _1= 2$, if remains to fill $n$ liters, by $G_{n} = F_{n+1}$ ways, and if $x_1 = 1$, it remains to fill $n+1$ liters, in $G_{n+1} = F_{n+2}$ ways. Thus $G_{n+2} = F_{n+1} + F_{n+2} = F_{n+3}$, and the induction is done. We can estimate $G_n$ in another ways. The solutions $(x_1,x_2,\ldots,x_k)$ can contains $0, 1, 2,\ldots, \lfloor n/2 floor$ times the $2$-liters container, i.e. there are $j$ integers $x_i$ among $x_1,\ldots, x_k$ such that $x_i = 2$, where $0 \leq j \leq \lfloor n/2 floor$, so its remains $n - 2j$ integers $x_i$ such that $x_i = 1$, thus $k = j + (n- 2j) = n-j$. There are $\binom{n-j}{j}$ ways to choose the $j$ emplacements of the $x_i = 2$ among $x_1,x_2,\ldots, x_k$, thus $$G_n = F_{n+1} = \sum_{j=0}^{ \lfloor n/2 floor} \binom{n-j}{j}.$$ So (1) is proven.


	1	1	2	3	5	$\dots$		$F_{n + 1}$	$F_{n + 2}$

1	0	0	0	0			$(\binom{0}{n})$	$(\binom{0}{n + 1})$
1	1	0	0
1	2	1	0
1	3	3	1
1
$⋮$
		$(\binom{n - 2}{2})$	$(\binom{n - 2}{3})$
	$(\binom{n - 1}{1})$	$(\binom{n - 1}{2})$
$(\binom{n}{0})$	$(\binom{n}{1})$
$(\binom{n + 1}{0})$

Exercise 4.4.4 ($F_{n+1} = \sum\limits_{i = 0}^{\lfloor n/2 \rfloor} \binom{n-i}{i}$)

Answers

Comments

Exercise 4.4.4 ($F_{n+1} = \sum\limits_{i = 0}^{\lfloor n/2 \rfloor} \binom{n-i}{i}$)

Answers

Comments

Add answer