Exercise 4.4.13 (Number of decompositions of $n$ in sum of odd numbers.)

Question

Show that the number of ways of writing a positive integer $n$ in the form $n = m_1+m_2+\cdots + m_k$ where $k$ is an arbitrary positive integer and $m_1,m_2,\ldots,m_k$ are arbitrary odd positive integers is $F_n$.

Richard Ganaye · Accepted Answer

ewcommand{\N}{\mathbb{N}}

\begin{proof} For every positive integer $n$, we write $G_n$ the number of ways of writing $n$ in the form $n = m_1+m_2+\cdots + m_k$, where $k$ is an arbitrary positive integer and $m_1,m_2,\ldots,m_k$ are arbitrary odd positive integers.

If $G_{n,i}$ denotes the number of such decompositions of $n$ satisfying $m_k = i$, where $i \leq n$ is an odd positive integer, then, as in Problem 12, 
$$G_n = \sum_{1\leq i \leq n,\, i \equiv 1 \,[2]}  G_{n,i} =\sum_{j = 0}^{\lfloor (n-1)/2 floor }G_{n, 2j +1}.$$
We note that if $1 \leq i \leq n$, then $G_{n,i}$ is the number of ways of writing $n -i $ in the form $n -i = m_1+m_2+\cdots + m_{k-1}$, where $k - 1$ is an arbitrary positive integer, so
$$G_{n,i} = G_{n-i},\qquad (1 \leq i \leq n-1,\ i 	ext{ odd}).$$
\begin{itemize}
\item If $n$ is odd, say $n = 2m +1$, then $G_n = G_{2m+1} = \sum\limits_{j =0}^m G_{n,2j+1}$.
   \begin{itemize}
   \item If $ j= m$, then the unique decomposition satisfying $m_k = 2j+1 = n$ is $n = m_1$, so  $k = 1$ and $G_{n,n} = G_{2m+1, 2m+1}= 1$.
   \item If $0 \leq j \leq m-1$, then $G_{n, 2j +1} = G_{n -2j - 1} = G_{2(m-j)}$.
   \end{itemize}
Therefore
 \begin{align*}
 G_{2m+1} &= 1 + G_2 + G_4 + \cdots + G_{2m}.
 \end{align*}
 \item If $n$ is even, say $n = 2m$, then $G_n =G_{2m} =  \sum\limits_{j =0}^{m-1} G_{n,2j+1}$.

For $ 0\leq j \leq m-1$,  $G_{n,2j+1} = G_{n - 2j - 1} = G_{2(m-j) - 1}$,

Therefore
\begin{align*}
G_{2m} &= G_1 + G_3 + \cdots + G_{2m-1}.
\end{align*}
To summarize, for every positive integer $m$,
\begin{align}
G_{2m}\ \  \, &=\  G_1 + G_3 + \cdots + G_{2m-1},\
 G_{2m+1} &= 1 + G_2 + G_4 + \cdots + G_{2m}.
\end{align}
\end{itemize}
Then $G_n$ is determined by these relation, knowing that $G_1 = 1, G_2 = 1$, since $1= 1$, and $2 = 1 + 1$ are the only decompositions of $1$ and $2$ in sum of odd integers.

Consider the proposition
$$\mathscr{P}(m) \iff \forall i \in \N,\ 1 \leq i < 2m \Rightarrow F_i = G_i.
$$
Since $G_1 = F_1 = 1$, $\mathscr{P}(1)$ is true.
Suppose that $\mathscr{P}(m)$ is true for some positive integer $m$. We know that $G_2 = F_2 = 1$, and for $m\geq 2$,  by (1) and (2) and the induction hypothesis,
\begin{align*}
G_{2m} &=G_1 + G_3 + \cdots + G_{2m-1}\
&= F_1 + F_3 + \cdots + F_{2m-1}\
&= 1+  F_1 + F_2 + \cdots + F_{2m-3}+ F_{2m-2}&(F_1 = 1)\
&= F_{2m}&(	ext{by Problem 5}),
\end{align*}
and, using $G_{2m} = F_{2m}$,
\begin{align*}
G_{2m+1} &= 1 + G_2 + G_4 + \cdots + G_{2m}\
&= 1 + F_2 + F_4 + \cdots + F_{2m}\
&= 1 + F_0 + F_1 + F_2 + F_3 + \cdots + F_{2m-2} + F_{2m-1}&(F_0 = 0)\
&= F_{2m+1} &(	ext{by Problem 5}).
\end{align*}
This shows $\mathscr{P}(m+1)$, and the induction is done. We conclude that for all positive integers $n$,
$$G_n = F_n.$$
\end{proof}

Exercise 4.4.13 (Number of decompositions of $n$ in sum of odd numbers.)

Answers

Comments

Exercise 4.4.13 (Number of decompositions of $n$ in sum of odd numbers.)

Answers

Comments

Add answer