# Strong Induction: parity of sum of odd numbers

This is the question:

Use strong mathematical induction to prove that for any integer $n \ge 2$, if $n$ is even, then any sum of $n$ odd integers is even, and if $n$ is odd, then any sum of $n$ odd integers is odd.

I know that $P(n)$ is the sentence:

“If $n$ is even, then any sum of $n$ odd integers is even, and if $n$ is odd, then any sum of $n$ odd integers is odd.”

If anyone could guide me a bit or provide some sort of formula, it be much appreciated!

• Can you prove it for $n=2$? Start by doing that. Do you know what you have to do then? – la flaca Feb 17 '17 at 16:40

The first step is to get this into mathematical form.

I would write it like this:

Let $(a_i)_{i=1}^n$ be odd integers. Then, for any positive integer $m$, $\sum_{i=1}^{2m} a_i$ is even and $\sum_{i=1}^{2m-1} a_i$ is odd.

Proof.

Note: All variables are integers.

The basic facts needed are that (1) every even number $a$ can be written in the form $a = 2b$; (2) every odd number $a$ can be written in the form $a = 2b+1$; (3) all numbers are either even or odd; (4) the sum of two even numbers is even; (5) the sum of an odd and even integer is odd; (6) the sum of two odd numbers is even.

Note: Facts (1) and (2) are definitions. A good exercise is to prove facts (3) through (6).

For $m=1$, this states that $a_1$ is odd and $a_1+a_2$ is even.

The first is true by assumption.

The second is true because the sum of two odd integers is even.

For the induction step, suppose it is true for $m$.

The statement for $m+1$ is $\sum_{i=1}^{2(m+1)} a_i$ is even and $\sum_{i=1}^{2(m+1)-1} a_i$ is odd.

For the first,

$\begin{array}\\ \sum_{i=1}^{2(m+1)} a_i &=\sum_{i=1}^{2m+2} a_i\\ &=\sum_{i=1}^{2m} a_i+a_{2m+1}+a_{2m+2}\\ &=(\sum_{i=1}^{2m} a_i)+(a_{2m+1}+a_{2m+2})\\ \end{array}$

and this is even (using fact 4) because $\sum_{i=1}^{2m} a_i$ is even by the induction hypothesis and $a_{2m+1}+a_{2m+2}$ is even by fact 6.

For the second,

$\begin{array}\\ \sum_{i=1}^{2(m+1)-1} a_i &=\sum_{i=1}^{2m+1} a_i\\ &=\sum_{i=1}^{2m-1} a_i+a_{2m}+a_{2m+1}\\ &=(\sum_{i=1}^{2m-1} a_i)+(a_{2m}+a_{2m+1})\\ \end{array}$

and this is odd (using fact 5) because $\sum_{i=1}^{2m-1} a_i$ is odd by the induction hypothesis and $a_{2m}+a_{2m+1}$ is even by fact 6.

You could also group the sum as $\sum_{i=1}^{2m} a_i+a_{2m+1}$; in this, the sum is even and $a_{2m+1}$ is odd, so their sum is odd.

I will prove the proposition "Given an even number $n\ge 2$, the sum of $n$ odd numbers is even and will leave to you the rest (which can be done essentially in the same way)

Let $n=2$. Suppose we have two odd numbers $n_1:=2k_1+1$ and $n_2:=2k_2+1$, with $k_1,k_2\in\mathbb{N}$. Then we have

$$n_1+n_2=2k_1+1+2k_2+1=2(k_1+k_2+1)$$ which is an even number. This establishes the base case. Now suppose the proposition is true for an even $n$ and you want to prove it for $n+2$ (the next even number). Suppose we have $n+2$ odd numbers $n_1,n_2,\dots , n_{n+2}$, i.e. $$n_i:=2k_i+1,$$ with $k_i\in\mathbb{N}$ for all $1\leq i\leq n+2$. We have $$\sum_{i=1}^{n+2}n_i=\sum_{i=1}^{n}n_i+n_{n+1}+n_{n+2}$$ By inductive hypothesis, $\sum_{i=1}^{n}n_i$ is an even number, i.e. there exists an $m\in\mathbb{N}$ such that $\sum_{i=1}^{n}n_i=2m$. Hence we have $$\sum_{i=1}^{n+2}n_i=2m+2k_{n+1}+1+2k_{n+2}+1=2(m+k_{n+1}+k_{n+2}+1)$$ which is an even number. Thus, by induction, we have just proved that, for any even number $n$, the sum of $n$ odd numbers is even.

I will leave to you to prove the fact that for any odd number $n$ the sum of $n$ odd numbers is odd in a similar fashion.

Tip: remember that if $p$ is an integer, then $2p$ is even and $2p+1$ is odd.

Using that, you can start with showing your proposition for $n=1$ and $n=2$. For $n=1$ it is obvious; any sum of one integer being the integer itself. For $n=2$, any 2 odd integers can be written $2p+1$ and $2q+1$ where $p$ and $q$ are integers (including 0 here); their sum is $2(q+p+1)$ which is even.

Now suppose the proposition is true for a specific integer $n$. Can you show it is then true for $n+1$?

The sum $\,S_{\large n}$ has same parity as $n\iff S_{\large n} = n + 2k\$ for some integer $k$

\begin{align} {\rm Suppose}\ \ \color{#c00}{S_n}\, &=\, \color{#c00}{S_{\large n} + 2k},\ \ \ \ {\rm i.e.}\ \ \color{#c00}{P(n)},\ \text{ our inductive hypothesis}\\[.2em] {\rm Then}\ \ \ S_{\large n+1} &=\, 2j\!+\!1\, +\, \color{#c00}{S_{\large n}}\ \ \ \text{arises by adding an odd integer\,2j\!+\!1\,$to$\,S_{\large n}} \\[.2em] &=\, 2j\!+\!1\, +\, \color{#c00}{n + 2k}\ \ \ \ \text{by our inductive hypothesis }\, \color{#c00}{P(n)}\\[.2em] &=\,\ n\!+\!1\, +\, 2(j\!+\!k),\ \ {\rm i.e.}\ \ P(n\!+\!1) \end{align}

Therefore $\ P(n)\,\Rightarrow\, P(n\!+\!1),\,$ which proves the inductive step.

Remark $\$ It boils down to $\, S_n \equiv \underbrace{1 + 1 + \cdots + 1}_{\large \text{sum of } \,n\,\ \rm odds\, \equiv\, 1}\!\equiv n\pmod{\!2}\,$ in modular language.