Sunday, November 18, 2018

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.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...