# Prove by induction that sum of an odd number of odd numbers is odd

Prove by induction that if $n$ is odd and $a_1,\,\cdots,\,a_n$ are odd, then \begin{aligned}\sum_{i = 1}^n a_i\end{aligned} is odd.

Progress: If $n = 1$ then $\sum_{i = 1}^1 a_i = a_1$, so the statement is ok. But then I can not understand how to proceed in this case.

• Is induction required? What have you tried? Where are you stuck? – TravisJ Jun 12 '15 at 16:45
• If $n = 1$ then $\sum_{i = 1}^1 a_i = a_1$ ... ok!! But then I can not understand how to proceed in this case. Can you help me, please? – TeM Jun 12 '15 at 16:53

There is really no need to use alternate indices.

1. Base Case: $n=1$.

$\sum_{i=1}^1 a_i = a_1$ is odd.

2. Induction Hypothesis:

Suppose that $\sum_{i=1}^n a_i$ is odd (for some $n\ge1$, $n$ is odd.)

3. Prove that the statement holds for the next odd number after $n$.

If $n$ is odd, then the next odd number is $n+2$.

$\sum_{i=1}^{n+2} a_i = \underbrace{\sum_{i=1}^{n} a_i}_{\text{first$n$terms}} + \underbrace{a_{n+1}+a_{n+2}}_{\text{last two terms}}$

By induction hypothesis, $\sum_{i=1}^{n} a_i$ is odd.

$a_{n+1} + a_{n+2}$ is even. (Sum of two odd numbers are even).

## So $\sum_{i=1}^{n} a_i + (a_{n+1} + a_{n+2})$ is odd. (Sum of an odd number and an even number is odd.)

Why does this proof work?

• we know that the sum is odd for $n=1$.
• knowing the sum is odd for $n=1$ implies that the sum is odd for $n=3$.
• knowing the sum is odd for $n=3$ implies that the sum is odd for $n=5$.
• knowing the sum if odd for $n=5$ implies that the sum is odd for $n=7$. ...

Base case: $a_1$ is odd, therefore it is okay.

Induction hypothesis: For some $k$, $\sum_{i=1}^{2k+1} a_i$ is odd.

Induction step: The sum of two odd numbers is even. Therefore $a_{2k+2}+a_{2k+3}$ is even. And even+odd=odd, and

$$\sum_{i=1}^{2k+3} a_i = \sum_{i=1}^{2k+1} a_i+a_{2k+2}+a_{2k+3}$$

Thus we can conclude it is true.

Proof without induction:

Let $n = 2m+1$ and let $a_i = 2k_i+1$ for $i=1,\cdots,n$. Then

$$\sum_{i=1}^n a_i = \sum_{i=1}^{2m+1} 2k_i+1 = 2\underbrace{\sum_{i=1}^{2m+1} k_i}_{S} + \sum_{i=1}^{2m+1} 1 = 2S + 2m+1 = 2(S+m)+1$$

• Great, I get it! But my problem is to understand how to proceed by induction ... – TeM Jun 12 '15 at 16:57

If induction is not required

There is an easy argument. Let your odd number of odd numbers be $a_{1},...,a_{2k+1}$ where $a_{i}=2k_{i}+1$ for each $1\leq i\leq 2k+1$. Then

$$\sum_{i=1}^{2k+1} a_{i} = \sum_{i=1}^{2k+1}(2k_{i}+1)=2\sum_{i=1}^{2k+1}k_{i} + \sum_{i=1}^{2k+1} 1 = 2\left(\sum_{i=1}^{2k+1}k_{i}\right) + 2k+1 = 2\left(k+\sum_{i=1}^{2k+1}k_{i}\right) + 1$$

which is clearly odd since it is one more than a clearly even number.