Use the Principle of Mathematical Induction to prove that 2 | (n2 − n) for all n ≥ 0.
or
prove that (n^2 − n) is divisible by 2 for all n ≥ 0
1. test if true for n = 1
1-1 = 0 , I guess that is true
2. assume that it is true for n = k, that is : k^2 - k is divisible by 2
3. show that it must be true for n = k+1
using the fact that if two numbers are divisible by some value of m then their
difference is also divisible by m
take the difference (k+1)^2 - (k+1) - (k^2 - k)
= k^2 + 2k + 1 - k - 1 - k^2 + k
= 2k, which is even, thus divisible by 2
Q.E.D.
Of course we could have just noticed that n^2 + n
= n(n+1), which would be 2 consecutive natural numbers
if n is even, then n+1 is odd
if n is odd, then n+1 is even, and the product of an odd times an even is always even
To prove that 2 divides (n^2 - n) for all n ≥ 0 using the Principle of Mathematical Induction, we need to follow these steps:
Step 1: Base Case:
Show that the statement holds for the base case, which is usually n = 0 or n = 1. Let's start with n = 0:
For n = 0, (0^2 - 0) = 0, and 2 divides 0 since 0 divided by any non-zero number is 0. Therefore, the statement holds for the base case.
Step 2: Inductive Hypothesis:
Assume that the statement holds true for some arbitrary value k, where k ≥ 0. That is, assume that 2 divides (k^2 - k).
Step 3: Inductive Step:
Now we need to prove that the statement also holds for the next consecutive value, which is k + 1. That is, we need to prove that 2 divides ((k+1)^2 - (k+1)).
Using binomial expansion, we can expand ((k+1)^2 - (k+1)) as follows:
((k+1)^2 - (k+1)) = (k^2 + 2k + 1 - k - 1)
= (k^2 + k)
= k(k + 1)
Since we assumed that 2 divides (k^2 - k) in the inductive hypothesis (the arbitrary value), we can write k^2 - k = 2m, where m is an integer.
Now let's substitute (k^2 - k) = 2m in k(k+1):
k(k+1) = 2m + k
= 2m + 2k/2
= 2(m + k/2)
The result (k(k+1)) is clearly divisible by 2, as it can be written as 2 times an integer (m + k/2).
Step 4: Conclusion:
By proving that if the statement holds for k, it also holds for k+1, we have established that the statement holds for all n ≥ 0 by the Principle of Mathematical Induction.
Therefore, we have shown that 2 divides (n^2 - n) for all n ≥ 0.
To prove that 2 | (n^2 - n) for all n ≥ 0 using the Principle of Mathematical Induction, we follow these steps:
Step 1: Base Case
We need to verify that the statement holds true for the base case, which is typically the smallest valid value of n. In this case, the smallest valid value of n is 0. Let's substitute n = 0 into the statement 2 | (n^2 - n):
2 | (0^2 - 0)
2 | 0
We can see that 2 divides 0 evenly, so the statement is true for the base case.
Step 2: Inductive Hypothesis
Assume that the statement is true for some arbitrary value k, where k is a non-negative integer. This assumption is called the inductive hypothesis. Let's assume that 2 | (k^2 - k), which means there exists an integer m such that k^2 - k = 2m.
Step 3: Inductive Step
Using the inductive hypothesis, we need to prove that the statement is also true for k + 1. Let's substitute k + 1 into the statement 2 | (n^2 - n):
2 | ((k + 1)^2 - (k + 1))
Expanding and simplifying the expression:
= 2 | (k^2 + 2k + 1 - k - 1)
= 2 | (k^2 + k)
The goal is to show that k^2 + k can be expressed as 2 multiplied by some integer.
We know that k^2 - k = 2m (by the inductive hypothesis).
Now, let's add k to both sides of the equation:
k^2 - k + k = 2m + k
k^2 = 2m + k
We can rewrite it as:
k^2 + k = 2m + k
So, k^2 + k can be expressed as 2 multiplied by the integer (m + k). Therefore, 2 | (k^2 + k).
Step 4: Conclusion
By proving the base case and the inductive step, we can conclude that 2 | (n^2 - n) is true for all n ≥ 0 by the Principle of Mathematical Induction.