0
$\begingroup$

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!

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

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.