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!
Best Answer
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.