4.1 Induction[27J]
[1XC] Let \(A⊇ ℕ\) and \(P(n)\) be a logical proposition that can be evaluated for \(n∈ A\). Suppose the following two assumptions are satisfied:
\(P(n)\) is true for \(n=0\) and
\(∀ n∈ ℕ, P(n)⇒ P(S(n))\) ;
then \(P\) is true for every \(n∈ ℕ\).
Let \(U=\{ n∈ ℕ:P(n)\} \), we know that \(0∈ U\) and that \(∀ x, x ∈ U⇒ S(x)∈ U\) , then from (N5) we conclude that \(U=\mathbb {N}\).
- E133
[1XF] Prove that \(∀ n∈ ℕ, n≠ S(n)\).
Hidden solution: [UNACCESSIBLE UUID ’1XJ’]
- E133
[1XG] Prove 1 by induction the following assertions:
\(∑_{k=1}^ nk=\frac{n(n+1)} 2\);
\(∑_{k=1}^ nk^ 2=\frac{n(n+1)(2n+1)} 6\);
\(∑_{k=1}^ nk^ 3=\frac{n^ 2(n+1)^ 2} 4\);
\(∑_{k=1}^ n\frac{1}{4k^ 2-1}=\frac{n}{2n+1}\);
\(∑_{k=1}^ n\frac{k}{2^ k}=2-\frac{n+2}{2^ n}\);
\(n!≥ 2^{n-1}\);
If \(x{\gt}-1\) is a real number and \(n∈ ℕ\) then \((1+x)^ n≥ 1+nx\) (Bernoulli inequality).
Hidden solution: [UNACCESSIBLE UUID ’1XK’]