1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Is induction required? What have you tried? Where are you stuck? $\endgroup$ – TravisJ Jun 12 '15 at 16:45
  • $\begingroup$ 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? $\endgroup$ – TeM Jun 12 '15 at 16:53
1
$\begingroup$

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$. ...
$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

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

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.

$\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.