Hints to exercises
When \(n = 3\), \(\sum\limits_{j=0}^n 4j+1 = 1 + 5 + 9 + 13= 28\) and \(2n^2 + 3n + 1 = 2\cdot 3^2 + 3 \cdot 3 + 1 = 28.\)
Look carefully at the stage from \(n=2\) to \(n=3\).
The sum of the first \(0\) positive integers is \((0^2 + 0)/2\). Or, if you prefer to start with something rather than nothing: The sum of the first \(1\) positive integers is \((1^2+1)/2\).
The sum of the first \(0\) positive odd numbers is \(0^2\). Or, the sum of the first \(1\) positive odd numbers is \(1^2\).
If \(1\) coin is flipped, the the probability that it is “heads” is \(1/2\). Or if we try it when \(n=0\), “If no coins are flipped the probability that all of them are heads is 1.” Does that make sense to you? Is it reasonable that we would say it is 100% certain that all of the coins are heads in a set that doesn’t contain any coins?
If \(n=1\) we have: “Every \(2 \times 2\) chessboard — with one square removed can be tiled perfectly by L-shaped trominoes.” This version is trivial to prove. Try formulating the \(n=0\) case.
In this modified version, \(P(0)\) is not going to imply \(P(1)\). and in fact, none of the odd numbered statements will be proven. If we change the basis so that we prove both \(P(0)\) and \(P(1)\), all the even statements will be implied by \(P(0)\) being true and all the odd statements get forced because \(P(1)\) is true.
A quick change would be to replace \(\forall k, \; P_k \implies P_{k+1}\) in the inductive step with \(\forall k, \; P_k \iff P_{k+1}\). While this would do the trick, a slight improvement is possible, if we treat the positive and negative cases for \(k\) separately.
The proof is by induction on \(n\).
Base case: (\(n=1\)) For the base case, note that when \(n=1\) we have \[ \sum_{k=1}^n k^3 = 1 \] and \[ \left( \frac{n(n+1)}{2} \right)^2 = 1.\]
Inductive step:
Suppose that \(m>1\) is an integer such that \[ \sum_{k=1}^m k^3 = \left( \frac{m(m+1)}{2} \right)^2 \]
Add \((m+1)^3\) to both sides to obtain \[ (m+1)^3 + \sum_{k=1}^m k^3 \;= \; \left( \frac{m(m+1)}{2} \right)^2 + (m+1)^3. \]
Thus \[\begin{align*} \sum_{k=1}^{m+1} k^3 & = \left( \frac{m^2(m+1)^2}{4} \right) + \frac{4(m+1)^3}{4} \\ & = \left( \frac{m^2(m+1)^2 + 4 (m+1)^3}{4} \right)\\ & = \left( \frac{(m+1)^2 (m^2 + 4(m+1))}{4} \right)\\ & = \left( \frac{(m+1)^2 (m^2 + 4m +4)}{4} \right)\\ & = \left( \frac{(m+1)^2 (m+2)^2}{4} \right)\\ & = \left( \frac{(m+1)(m+2)}{2} \right)^2 \end{align*}\]
\(\frac{n\cdot(n+1)\cdot(2n+1)\cdot(3n^2+3n-1)}{30}\)
The formula is \(\frac{n(n+1)(n+2)}{6}\).
The proof is by induction on \(n\).
Base case: (\(n=1\)) For the base case, note that when \(n=1\) we have \[\sum_{i=1}^n (-1)^{i-1} i^2 \;= \; 1 \] and also \[ (-1)^{n-1} \frac{n(n+1)}{2} \;= \; 1. \]
Inductive step:
Suppose that \(k>1\) is an integer such that \[ \sum_{i=1}^k (-1)^{i-1} i^2 \;= \; (-1)^{k-1} \frac{k(k+1)}{2}. \]
Adding \((-1)^{k} (k+1)^2\) to both sides gives \[\begin{align*} \sum_{i=1}^{k+1} (-1)^{i-1} i^2 & = (-1)^{k-1} \frac{k(k+1)}{2} + (-1)^{k} (k+1)^2 \\ & = (-1)^{k-1} \frac{k(k+1)}{2} - (-1)^{k-1} (k+1)^2 \\ & = (-1)^{k-1} \left( \frac{k(k+1)}{2} - \frac{2(k+1)^2}{2} \right) \\ & = (-1)^{k} \left( \frac{2(k+1)^2}{2} - \frac{k(k+1)}{2} \right) \\ & = (-1)^{k} \frac{(k+1)(2(k+1)-k)}{2} \\ & = (-1)^{k} \frac{(k+1)(k+2)}{2} \\ \end{align*}\]
Notice that the problem statement didn’t specify the domain – but the smallest value of \(n\) that gives a non-empty product on the left-hand side is \(n=2\). Below is a sketch of the proof:
Base case: (\(n=2\)) For the base case, note that when \(n=2\) we have \[ \prod_{i=2}^2 \left(1 - \frac{1}{i}\right) \quad = \quad \left(1 - \frac{1}{2}\right) \quad = \quad 1/2 \] and the right-hand side (\(1/n\)) also evaluates to \(1/2\).
Inductive step:
Suppose that \(k\geq2\) is an integer such that \[ \prod_{i=2}^k \left(1 - \frac{1}{i}\right) = \frac{1}{k}. \] Then, \[\begin{align*} \prod_{i=2}^{k+1} \left(1 - \frac{1}{i}\right) & = \left(1 - \frac{1}{k+1}\right) \; \cdot \; \prod_{i=2}^{k} \left(1 - \frac{1}{i}\right) \\ & = \left(1 - \frac{1}{k+1}\right) \; \cdot \; \frac{1}{k} \\ & = \frac{1}{k+1}. \end{align*}\]
The final line skips over a tiny bit of algebraic detail. You may feel more comfortable if you fill in those steps.
The proof is by induction on \(n\).
Base case: (\(n=0\)) For the base case, note that when \(n=0\) we have \[ \sum_{j=0}^{n}(4j+1) = (4\cdot 0 + 1 = 1 \] and \[ 2n^2+3n+1 = 2\cdot 0^2 +3\cdot 0 + 1 = 1. \]
Inductive step:
Suppose that \(k \geq 0\) is an integer such that \[ \sum_{j=0}^{k}(4j+1) \; = \; 2k^{2}+3k+1. \]
(We want to show that \(\displaystyle \sum_{j=0}^{k+1}(4j+1) = 2(k+1)^{2}+3(k+1)+1\).)
So consider the sum \(\displaystyle \sum_{j=0}^{k+1}(4j+1)\): \[\begin{align*} \sum_{j=0}^{k+1}(4j+1) & = 4(k+1)+1 + \sum_{j=0}^{k}(4j+1) \\ & = 4(k+1)+1 + 2k^{2}+3k+1 \\ & \vdots \\ \end{align*}\]
Notice that the last line given in the proof is where the inductive hypothesis gets used. The actual last line of the proof is fairly easy to determine. (Hint: it is given in the “We want to show” sentence.) So now you just have to fill in the gaps.
The proof is by induction on \(n\).
Base case: (\(n=0\)) For the base case, note that when \(n=0\) \[ \sum_{j=0}^{n} \frac{1}{(2i-1)(2i+1)} \] contains no terms. Thus its value is 0.
Note that \(\displaystyle \frac{n}{2n+1}\) also evaluates to 0 when \(n=0\).
Inductive step:
By the inductive hypothesis, we may write \[ \sum_{i=1}^{k} \frac{1}{(2i-1)(2i+1)} = \frac{k}{2k+1}. \]
Adding \(\displaystyle \frac{1}{(2(k+1)-1)(2(k+1)+1)}\) to both side of this gives \[ \sum_{i=1}^{k+1} \frac{1}{(2i-1)(2i+1)} = \frac{k}{2k+1} + \frac{1}{(2(k+1)-1)(2(k+1)+1)}. \]
To complete the proof we must verify that \[ \frac{k}{2k+1} + \frac{1}{(2(k+1)-1)(2(k+1)+1)} = \frac{k+1}{2(k+1)+1}. \]
Note that \[\begin{align*} & \frac{k}{2k+1} + \frac{1}{(2(k+1)-1)(2(k+1)+1)} \\ = \; & \frac{k}{2k+1} + \frac{1}{(2k+1)(2k+3)}\\ = \; & \frac{k(2k+3)}{(2k+1)(2k+3)} + \frac{1}{(2k+1)(2k+3)}\\ = \; & \frac{k(2k+3)+1}{(2k+1)(2k+3)} \\ = \; & \frac{2k^2+3k+1}{(2k+1)(2k+3)} \\ = \; & \frac{(2k+1)(k+1)}{(2k+1)(2k+3)} \\ = \; & \frac{k+1}{2k+3} = \frac{k+1}{2(k+1)+1} \end{align*}\] as desired.
The proof is by induction on \(n\).
Base case: (\(n=0\))
For the base case, note that when \(n=0\) \[ \sum_{i=0}^{n} (F_i)^2 = 1. \]
Note also that \(\displaystyle F_n \cdot F_{n+1} = F_0 \cdot F_1 = 1 \cdot 1 = 1\).
Inductive step:
By the inductive hypothesis, we may write \[ \sum_{i=0}^k (F_i)^2 = F_k \cdot F_{k+1}. \]
Adding \((F_{k+1})^2\) to both sides gives \[ \sum_{i=0}^{k+1} (F_i)^2 = F_k \cdot F_{k+1} + (F_{k+1})^2. \]
Finally, note that (using factoring and the defining property of the Fibonacci numbers) we can show that \[\begin{align*} F_k \cdot F_{k+1} + (F_{k+1})^2 & = F_{k+1} \cdot (F_k + F_{k+1}) \\ & = F_{k+1} \cdot F_{k+2} \end{align*}\]
So the inductive step has been proved and the result follows by PMI.
The proof is by induction on \(x\).
Base case: (\(x=0\))
The base case is trivial since, when \(x=0\), \(x^3-x\) evaluates to \(0\) and every natural number is a divisor of \(0\).
Inductive step:
In the inductive step we want to show that \(\forall k \in {\mathbb N}, 3 \!\mid\!k^3 - k \implies 3 \!\mid\!(k+1)^3 - (k+1)\). So, let \(k\) be an arbitrary natural number such that \(3 \!\mid\!k^3 - k\).
Note that \[\begin{align*} (k+1)^3 - (k+1) & = (k^3 + 3k^2+ 3k +1) - (k+1) \\ & = (k^3 - k) + (3k^2 + 3k). \end{align*}\]
By the inductive hypothesis (and the definition of divisibility), we know that there is an integer \(q\) such that \(k^3-k = 3q\). So, by substitution, we obtain \[ (k+1)^3 - (k+1) = 3q + 3k^2 + 3k = 3 \cdot (q + k^2 + k).\]
Finally, \(q+k^2-k\) (being the sum of integers) is certainly an integer, so by the definition of divisibility, it follows that \((k+1)^3 - (k+1)\) is divisible by 3.
Look at how you can get \(13\) and \(14\).
Similar idea as in the previous question.