Induction.?

Question

Prove with induction that:
1)n^3 + 5n is divided by 6 (without a remainder)
2)7^n – 3^n is divided by 4 (without a remainder)

Answer 1

1)

Prove that n^3 + 5n is divisible by 6 for all natural numbers n.

Base case: Let n = 1.
Then, n^3 + 5n = 1^3 + 5(1) = 6, and 6 is obviously divisible by 6.

Induction Hypothesis: Assume that k^3 + 5k is divisible by 6.

{We want to prove that (k + 1)^3 + 5(k + 1) is divisible by 6}

BUT, what is (k + 1)^3 + 5(k + 1) equal to?

First, let's factor (k + 1) out of the terms.
(k + 1)^3 + 5(k + 1) = (k + 1) [ (k + 1)^2 + 5 ]

Expanding the terms in the second set of brackets,

= (k + 1) [ k^2 + 2k + 1 + 5]
= (k + 1) (k^2 + 2k + 6)

Now, let's expand this out.

= k^3 + 2k^2 + 6k + k^2 + 2k + 6

Group like terms,

= k^3 + 3k^2 + 8k + 6

At this point, I'm going to decompose 8k into 5k + 3k, and I'm going to rearrange the terms.

= k^3 + 5k + 3k^2 + 3k + 6

Now, to make something obvious, I'm going to split this into three parts using parentheses.

= (k^3 + 5k) + (3k^2 + 3k) + 6
= (k^3 + 5k) + (3k(k + 1)) + 6

Let's examine these three parts:
k^3 + 5k is divisible by 6, by our induction hypothesis.
3k(k + 1) is divisible by 6, because k(k + 1) is even (since it is a product of an odd and even number).
6 is obviously divisible by 6.

We have the sum of three things divisible by 6, and it follows that their sum is divisible by 6.

Therefore, (k + 1)^3 + 5(k + 1) is divisible by 6, meaning the formula holds true for n = k + 1.
Thus, by the Principle of Mathematical Induction, n^3 + 5n is divisible by 6 for all natural numbers n.

(2) Prove 7^n - 3^n is divisible by 4 for all natural numbers n.

Base case: Let n = 1. Then
7^n - 3^n = 7^1 - 3^1 = 7 - 3 = 4, which is obviously divisible by 4.

Induction Hypothesis: Assume the formula holds true for n = k. That is,
assume 7^k - 3^k is divisible by 4.

{We want to prove that 7^(k + 1) - 3^(k + 1) is divisible by 4}

But what does 7^(k + 1) - 3^(k + 1) equal to?

7^(k + 1) - 3^(k + 1)

We can decompose 7^(k + 1) as (7^k)(7^1), or (7)(7^k), and likewise with the 3^(k + 1).

(7) 7^k - (3) 3^k

I'm going to change the 7 into (3 + 4)

(3 + 4) 7^k - (3) 3^k

Distributing the 7^k with the (3 + 4),

(3)7^k + (4)7^k - (3)3^k

Rearranging the terms,

(3)7^k - (3)3^k + (4)7^k

Factoring out 3 from the first two terms,

3(7^k - 3^k) + (4)7^k

Now, let's take a look at these two terms being added:

Since (7^k - 3^k) is divisible by 4 by our induction hypothesis, it follows that 3(7^k - 3^k) is divisible by 4 as well.

(4)7^k is OBVIOUSLY divisible by 4.

Therefore, the sum of two terms divisible by 4 is also divisible by 4, and it subsequently follows that
7^(k + 1) - 3^(k + 1), the expression this began as, is divisible by 4.

Therefore, by the principal of mathematical induction, 7^n - 3^n is divisible by 4 for all natural numbers n (or, n >= 1).

Answer 2

1) For n=0 we have n³ + 5n = 0, divisible by 6.
Given n³ + 5n divisible by 6, then
(n+1)³ + 5(n+1) = n³ + 3n² + 3n + 1 + 5n + 5
= (n³ + 5n) + (3n² + 3n + 6)
= 3(n² + n + 2) mod 6
= 3[n(n+1) + 2] mod 6
= 3 * [an even number + 2] mod 6
= a multiple of 6.

2) Works for n=0 as well.
Given 7^n - 3^n = 0 mod 4, then
7^(n+1) - 3^(n+1)
= 7*7^n - 3*3^n
= 7*7^n - 3*3^n - 4*3^n + 4*3^n
= 7*7^n - 7*3^n + 4*3^n
= 7(7^n - 3^n) + 4*3^n
= 7*multiple of 4 + 4*3^n.
QED.