Exercise 4.5.12* (If $1 \leq k \leq (n^2 + n)/2$, there is a subset of the set $[\![1, n]\!]$ whose sum is $k$)

Question

Let $n$ and $k$ be positive integers such that $1 \leq k \leq (n^2 + n)/2$. Prove that there is a subset of the set $\{1,2,3,\ldots,n\}$ whose sum is $k$.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

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

\begin{proof} 
We prove this property by induction on $n$. We write $T_n = \frac{n(n+1)}{2} = 1 + 2 + \cdots +n$ the $n$-th triangular number. Consider the proposition
$$\mathscr{P}(n) \iff \forall k \in [\![1, T_n]\!],\ \exists I \subseteq [\![1, n ]\!],\  k = \sum_{i \in I} i.$$
\begin{itemize}
\item If $n = 1$, the only integer $k$ such that $k \in [\![1, T_1]\!$ is $k = 1$, and $k = 1 =  \sum_{i \in \{1\}} i$, where $I = \{1\} \subseteq [\![1, n ]\!] = \{1\}$, so $\mathscr{P}(1)$ is true.
\item Suppose now that $\mathscr{P}(n-1)$ is true for some $n \geq 2$. Let $k$ be any element of  $[\![1, T_n]\!]$. 
   \begin{itemize} 
  \item If $k \leq T_{n-1}$, then the induction hypothesis $\mathscr{P}(n-1)$ shows that  $n =  \sum_{i \in I} i$, where $I \subseteq [\![1, n-1 ]\!] \subseteq [\![1, n]\!]$.
  \item If $k = T_n$, then $k =  \sum_{i \in [\![1, n]\!]} i$.
  \item If $T_{n-1} < k < T_n$, then $k = T_n - h$ for some $h$ such that $1 \leq h < T_n - T_{n-1} = n$. Therefore
  $$k = T_n - h  = \left( \sum_{i \in [\![1, n]\!]} i ight)  - h =  \sum_{i \in [\![1, n]\!] - \{h\}} i.$$
 So $ k = \sum_{i \in J} i$, where $J =  [\![1, n]\!] - \{h\} \subseteq  [\![1, n]\!]$.
  \end{itemize}
  \item In all cases, $k  = \sum_{i \in I} i$ for some $I \subseteq [\![1, n]\!]$, so $\mathscr{P}(n)$ is true, and the induction is done.
\end{itemize}
This shows that for every  positive integer $n$, every $k \in [\![1, (n^2+n)/2]\!]$ is a sum $k= \sum_{i \in I} i$ for some $I\subseteq [\![1, n]\!]$.
\end{proof}
Note: Following this algorithm, we give a function in sagemath  which return the list of elements of $I \subseteq [\![1, n]\!]$, where $n$ is the least integer such that $k \leq n(n+1)/2$.
\begin{verbatim}
def find_n(k):
    """find n such that T_(n-1)< k <= T_n"""
    return ceil(sqrt(2 * k + 0.25) - 0.5)
        
def representation(k):
    """return a list of elements i <= n whose sum is k, 
    where n is the least integer such that k <= T_n"""
    n = find_n(k)
    Tn = (n * (n + 1))// 2
    l = list(range(1, n + 1))
    h = Tn - k
    if h >0: l.remove(h)
    return l
    
representation(18)   
            [1, 2, 4, 5, 6]

\end{verbatim}

Exercise 4.5.12* (If $1 \leq k \leq (n^2 + n)/2$, there is a subset of the set $[\![1, n]\!]$ whose sum is $k$)

Answers

Comments

Exercise 4.5.12* (If $1 \leq k \leq (n^2 + n)/2$, there is a subset of the set $[\![1, n]\!]$ whose sum is $k$)

Answers

Comments

Add answer