0
$\begingroup$

Let property

$P(n)= \begin{cases} \text{if $n$ is even, then any sum of $n$ odd integers is even} \\ \text{if $n$ is odd, then any sum of $n$ odd integers is odd} \end{cases}$

We need to show that $P(n)$ is true for all integers $n\geq2$ by strong induction.

Basis

P(2) is true since the sum of two odd numbers is always even. Moreover, P(3) is true since the sum of two odds is even,and the sum of an additional odd results in an odd integer.

Inductive hypothesis

Let k be any integer with $ k>3$, and suppose that for all integers i with $2 \leq i < k, P(i) \text{ is true. We wish to show that } P(k)\text{ is true.}$

There are two cases: k is odd or k is even.

Case 1) In this case k is odd, so consider the set S of k elements: $\{a_1,a_2,...,a_k\}$. Now let A and B be subsets of S with $A\cap B = \emptyset \text{ and } S=A \cup B .$ Either $N(A) \text{ or } N(B) \text{ is odd.}$ Without loss of generality, say $N(A)$ is odd, then N(B) is even.

By the inductive hypothesis, the sum of the odd integers in set A is odd, and the sum of the odd integers in set B is even, and thus the total summation is odd.

Case 2) In this case k is even and can be proven in a similar fashion as in case 1.

My concern main concern about this proof is its validity, and in particular I'm concerned up to the sentence

Now let A and B be subsets of S with $A\cap B = \emptyset \text{ and }$ $ S=A \cup B .$

because I sense that it's too general. For instance, what if $A=\{a_1,a_2,..., a_k\} \text{ and } B=\{ \}$, then the inductive hypothesis later on wouldn't be able to be used?

$\endgroup$
0
$\begingroup$

You don't need to show this for every possible division of $S$ into sets $A$ and $B$. You just need one such division, with neither A nor B empty, for the induction to follow.

Let $A = \{a_1, a_2, ... a_{n-1}\}, B = \{a_n\}$. By the induction hypothesis, we know that $\sum A$ is odd when $n$ is even and is even when $n$ is odd. Therefore $\sum S = \sum A + a_n$ is even for $n$ even and odd for $n$ odd, because $a_n$ is odd.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy