discrete mathematics - 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!

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.