# Induction Problem Help, writing equation

There are $$n$$ piles of marbles and that every pile has a different number of marbles. We want to prove that the sum of the number of marbles in all the piles is greater than or equal to $$\frac{n(n + 1)}{2}$$, without knowing anything beyond the fact that each pile has a different number of marbles. Use induction to prove this fact for any positive integer $$n$$.

I'm having trouble writing the initial equation to solve and getting started. $$\sum_{i=1}^{n}$$ $$\geq \frac{n(n + 1)}{2}$$ is what I have so far where the base case is n = 1, but should I say have a variable for the number of piles so that it's written like $$\sum_{i=1}^{p}~$$ p $$~\geq \frac{n(n + 1)}{2}$$ where p is the sum of the piles and then the base case would be p = 1?

• Note that the sum you looking for is greater then or equal to $1 + 2 + \cdots + n$: let $p_1,p_2,...,p_n$ your piles and assume that $p_1$ has $k$ numbers of marbles. Then, WLOG, $p_1 < p_2 < \cdots < p_n$. Thus, the smallest number is when $k = 1$ and $p_i$ has $i$ marbles. Thus, if you show that $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$, your problem is solved. Feb 22, 2021 at 6:22

Base case : (Assuming that each pile has non zero number of marbles) Clearly the claim is true for $$1$$ pile .
Induction Hypothesis : Suppose that the sum of number of marbles in each pile is greater than $$\frac{n(n+1)}{2}$$ for some arbitrary $$n$$ piles.
Induction step : Now suppose that there are $$n + 1$$ piles. Obviously the last pile has to contain at least $$n + 1$$ marbles as the number of marbles in each pile is distinct. Let the number of marbles in last pile be $$p$$. We have that $$p \geq n+1$$ . Hence $$\frac{n(n+1)}{2} + p \geq \frac{n(n+1)}{2} + n + 1$$ As there are at least $$\frac{n(n+1)}{2}$$ marbles when there are $$n$$ piles from our hypothesis, we are done.