Strong induction?

Question

The question is "Show using strong induction, that any sum of 2 or more even integers is even". Now, I'm fine with regular induction, but I'm lost in the notation of strong induction. So far, I have:

BASE: (we will use 2 as our even number)

n=2 by sequence definition, A2 = 4 (even)

n=3 by sequence definition, A3 = 6 (even)

Thus, we have P(2) and P(3)

I'm not sure where to go from here, if someone could lead me in the right direction, that would be great

Answer 1

The induction should be on the number of numbers, not the numbers themselves. Here's the proof you're looking for, for what it's worth:

The proof is by induction on the number of even numbers to be summed.

Base case: Let a and b be any two even numbers. Because a and b are even, we can write a = 2c and b = 2d for some integers c and d (not necessarily even). We then have a + b = 2c + 2d = 2(c + d). Since a + b = 2e, where e = c + d is some integer, then a + b is even by definition.

Induction hypothesis: Assume that the sum of any collection of up to k >= 2 even numbers is even.

Induction step: We must show that the sum of any collection of k + 1 even numbers is also even. Let {n_1, n_2, ..., n_k, m} be any collection of k + 1 even numbers. We must show that n_1 + n_2 + ... + n_k + m is even. By the associative and commutative properties of addition, we can safely write this as (n_1 + n_2 + ... + n_k) + m without changing the value of the expression. From the induction hypothesis, we know that p = n_1 + n_2 + ... + n_k must be even, since it is the sum of a collection of up to k even numbers. We now have p = 2x, m = 2y, and n_1 + n_2 + ... + n_k + m = p + m = 2x + 2y = 2(x + y) = 2z for z = x + y, and therefore we know that n_1 + n_2 + ... + n_k + m must be even.

This concludes the proof by induction.