Problem 19 - Algebra and Trigonometry

Question

Use the Principle of Mathematical Induction to show that the given statement is true for all natural numbers \(n\). $$ n^{2}+n \text { is divisible by } 2 $$

Step-by-Step Solution

Answer

Since both the base case and the induction step hold, \( n^2 + n \) is divisible by 2 for all natural numbers \( n \).

Step 1 - Verify Base Case

First, check if the statement is true for the initial value, typically n = 1. Substitute n = 1 into the statement: \[ 1^2 + 1 = 2 \] Since 2 is divisible by 2, the base case holds.

Step 2 - Assume True for k

Assume the statement is true for some arbitrary natural number k. This means we assume: \[ k^2 + k \text{ is divisible by 2} \] This assumption is called the induction hypothesis.

Step 3 - Prove for k + 1

Under the induction hypothesis, show that the statement is true for k + 1. Start by substituting k + 1: \[ (k + 1)^2 + (k + 1) \] Expand this expression: \[ (k^2 + 2k + 1) + (k + 1) = k^2 + 2k + 1 + k + 1 = k^2 + 3k + 2 \] Notice that: \[ k^2 + 3k + 2 = (k^2 + k) + 2(k + 1) \] Since \( k^2 + k \) is divisible by 2 (by the induction hypothesis), and \( 2(k + 1) \) is clearly divisible by 2, their sum is also divisible by 2.

Step 4 - Conclude the Proof

Since both the base case and the inductive step have been proven, by the principle of mathematical induction, the statement \( n^2 + n \text{ is divisible by } 2 \) is true for all natural numbers \( n \).

Key Concepts

Base Case

Understanding the base case is the first crucial step in Mathematical Induction. In our exercise, the base case requires us to verify if the statement holds true for the smallest natural number, which is typically 1.
For our specific statement, which is 'n² + n is divisible by 2,' we need to test it with n = 1.
When we substitute n = 1, the expression becomes: Substituting, we get:

Induction Hypothesis

The induction hypothesis is the assumption stage of Mathematical Induction. Here, we assume that the statement we're trying to prove is true for some arbitrary natural number k.
This step builds a bridge between the initial case and the next. It allows us to generalize the proof for a specific value, making it easier to extend to a broader range.
In our exercise, we assume that for some arbitrary natural number k, the expression 'k² + k is divisible by 2' holds true.
This assumption forms the groundwork to move on to the next step, the Inductive Step.

Inductive Step

The Inductive Step is the crux of Mathematical Induction. This is where we prove that if our statement holds true for an arbitrary natural number k (our induction hypothesis), it must also hold true for k + 1.
For our exercise, we start by substituting k + 1 into the statement: Expand: Rearrange: Since our induction hypothesis tells us that k² + k is divisible by 2, and 2(k + 1) is clearly divisible by 2, we can conclude that k² + 3k + 2 is also divisible by 2.

Natural Numbers

In the context of Mathematical Induction, the term 'natural numbers' refers to the set of positive integers starting from 1, 2, 3, and so on.
The principle of Mathematical Induction applies to statements that need to be proven for all natural numbers. This is why we start with a base case (usually n = 1) and then use the induction hypothesis and inductive step to prove the statement holds for all subsequent natural numbers.
Natural numbers are a fundamental concept in number theory and are used extensively in proofs and problem-solving exercises such as the one we're discussing.