Exercises on natural numbers and induction

Prove by induction that for every positive integer n, ∑ⁿ_{_k=0} (4k + 1) = (2n + 1)(n + 1)
Prove by induction that for every positive integer n

1² + 2² + 3² + ... + n² = n(n+1)(2n+1)/6
Prove by induction that for every positive integer n, the power set 𝓟(X) of a finite set X with n elements has 2ⁿ elements.
Prove by mathematical induction the formula for partial sums of a geometric series: s_n = a[(1 −q^{n +1})/(1 − q)].
Prove the binomial theorem;

Solutions

For n = 0, we have 1 = 1. We suppose the relation true for n−1 and we prove it for n.

∑ⁿ_{_k=0} (4k + 1) = ∑ⁿ⁻¹_{_k=0} (4k + 1) + 4n +1 = (2n + 1)(n + 1) (2n + 1)(n + 1)[2(n−1) + 1] ⋅ n + 4n + 1 = (2n − 1) ⋅ n + 4n + 1 = 2n² −n + 4n +1 = 2n² + 3n +1 = (2n+1) ⋅ (n+1) ■
For n = 1 is true. We suppose 1² + 2² + 3² + ... + (n − 1)² = ((n−1)n(2(n−1) + 1))/6 and prove it for n.

1² + 2² + 3² + ... + n² = ((n−1)n(2(n−1) + 1))/6 + n² = n(n+1)(2n+1)/6. ■
It's true for n = 0, you could use that as the base case, X has exact one (= 2⁰) the empty subset. We suppose true that every set X with n−1 elements has 2ⁿ⁻¹ subsets. The set {X} \ {x} has n−1 elements, hence it has 2ⁿ⁻¹ subsets. To obtain the subsets of X we must add to each of these 2ⁿ⁻¹ subsests the element x, obtaining another 2ⁿ⁻¹ subsests thus in total 2ⁿ⁻¹ + 2ⁿ⁻¹ = 2ⁿ subsests.
Clearly P(0) is true; So we suppose that P(n) is true and show that P(n +1) is true as well
$s_{n + 1} = \sum_{k = 0}^{n} a q^{k} + a q^{n + 1} = a \frac{1 - q^{n + 1}}{1 - q} + a q^{n + 1} = \frac{a (1 - q^{n + 1}) + a q^{n + 1} (1 - q)}{1 - q} = \frac{a (1 - q^{n + 2})}{1 - q}$
For n = 0, the result is trivial as (a + b)⁰ = 1 = (0 0) a⁰b⁰. Assume that it holds when n = k for some integer k ≥ 0, that is
$(a + b)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) a^{n - k} b^{k}$
and we try to prove it for n + 1. Observe that $\begin{aligned} (a + b)^{n + 1} & = (a + b) (a + b)^{n} \\ = (a + b) \sum_{k = 0}^{n} (\binom{n}{k}) a^{n - k} b^{k} (by the inductive hypothesis) \\ = \sum_{k = 0}^{n} (\binom{n}{k}) a^{n - k + 1} b^{k} + \sum_{k = 0}^{n} (\binom{n}{k}) a^{n - k + 1} b^{k + 1} \\ = a^{n + 1} + [(\binom{n}{1}) + (\binom{n}{0})] a^{n} b + [(\binom{n}{2}) + (\binom{n}{1})] a^{n - 1} b^{2} + \dots + [(\binom{n}{n}) + (\binom{n}{n - 1})] a b^{n} + b^{n + 1} \end{aligned}$
Applying
$(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k}) 1.4.1$
we have that
$(a + b)^{n + 1} = (\binom{n + 1}{0}) a^{n + 1} + (\binom{n + 1}{1}) a^{n} b + (\binom{n + 1}{2}) a^{n - 1} b^{2} + \dots + (\binom{n + 1}{n}) a b^{k} + (\binom{n + 1}{n + 1}) b^{n + 1}$
as desired. ■

«Set theory Index Relations »