Exercise 4.4.12 (Number of ways of writing $n$ in the form $n = m_1 + m_2 + \cdots + m_k$)

Question

Let $r(n)$ be the number of ways of writing a positive integer $n$ in the form $n = m_1 + m_2 + \cdots + m_k$ where $m_1, m_2, \ldots, m_k$ and $k$ are arbitrary positive integers. Show that $r(n) = 1 + r(1) + r(2) + \cdots + r(n-1)$ for $n \geq 2$. Deduce that $r(n) = 2 r(n-1)$ for $n \geq 2$. Conclude that $r(n) = 2^{n-1}$ for all positive integers $n$.

Richard Ganaye · Accepted Answer

Note that here the order of $(m_1,m_2,\ldots,m_k)$ is relevant (if not, we obtain the number $p(n)$ of {\bf partitions} of $n$, which is another problem of Number Theory). 
So $(1,3,1)$  and $(3,1,1)$ are two distinct decompositions of $n$.

\begin{proof} 
Let $n$ be a positive integer. We  search the cardinality of $A$, where $A$ is the set of tuples $(m_1, m_2,\ldots,m_k)$ such that $n = m_1+ m_2 + \cdots + m_k$.

Suppose that $n\geq 2$. Consider the sets $A_i \subseteq A$ of such tuples $(m_1,m_2,\ldots,m_k)$ of positive integers satisfying $m_1 = i$. Since $n = m_1 + m_2+ \cdots + m_k$, we have $1 \leq m_1 \leq n$, thus $A  = \bigcup\limits_{j=1}^n A_j$ (disjoint union). So
$$r(n) = |A| = \sum_{j=1}^{n} |A_j|.$$

If $i= n$, there is a unique tuple $(n)$ satisfying the condition, so $|A_1| = 1$.

More generally,  if $1 \leq i \leq n - 1$, the cardinality of $A_{n-i}$ is equal to the number of tuples $m_2,\ldots, m_k $ such that $m_2 + \cdots + m_k = i$, where $k\geq 2$ is arbitrary, thus
$$|A_{n-i}| = r(i).$$
Therefore
\begin{align*}
|A| &= \sum_{j=1}^{n} |A_j| \
&= |A_n| +\sum_{j=1}^{n-1} |A_j|\
&= 1 + \sum_{i=1}^{n - 1} |A_{n-i}|&(i = n-j)\
&=1+ \sum_{i=1}^{n - 1} r(i).
\end{align*}
So
$$r(n) = 1 + r(1) + r(2) + \cdots + r(n-1)\qquad (n \geq 2).$$

Then for all $n \geq 3$,
\begin{align*}
r(n) - r(n-1) &= \left( 1+ \sum_{i=1}^{n - 1} r(i) ight) - \left( 1+ \sum_{i=1}^{n - 2} r(i) ight)\
&= r(n-1).
\end{align*}
Therefore $r(n) = 2 r(n-1)$ for $n\geq 3$. Note that $r(1) = 1$, and $r(2) = 1 + r(1) = 2$, so for every $n \geq 2$, 
$$r(n) = 2 r(n-1).$$
By induction, we obtain
$$r(n) = 2^{n-1} r(1).$$
Since $r(1) = 1$,
$$r(n) = 2^{n-1}.$$

\end{proof}

Note: Following the preceding algorithm to find $A_i$, I give a recursive python program to obtain all decompositions of $n$:
\begin{verbatim}
def decomposition(n):
    if n == 1:
        return [[1]]
    else: 
        dec = [[n]]
        for i in range(1,n):
            for l in decomposition(n-i):
                dec.append([i] + l)
        return dec
        
decomposition(5)
[[5],
 [1, 4],
 [1, 1, 3],
 [1, 1, 1, 2],
 [1, 1, 1, 1, 1],
 [1, 1, 2, 1],
 [1, 2, 2],
 [1, 2, 1, 1],
 [1, 3, 1],
 [2, 3],
 [2, 1, 2],
 [2, 1, 1, 1],
 [2, 2, 1],
 [3, 2],
 [3, 1, 1],
 [4, 1]]
 \end{verbatim}

Exercise 4.4.12 (Number of ways of writing $n$ in the form $n = m_1 + m_2 + \cdots + m_k$)

Answers

Comments

Exercise 4.4.12 (Number of ways of writing $n$ in the form $n = m_1 + m_2 + \cdots + m_k$)

Answers

Comments

Add answer