# Simple proof by induction problems

I just started learning proof by induction and I have come across 2 problems that I am not sure if am doing right. The first one is Prove that $$11^n - 1$$ is dividable by $$10$$.

I started with $$n = 0, 11^0 - 1 = 0$$, is dividable by $$10$$

I did the same for $$1$$ and $$2$$, what is the next step here?

and the second one is $$\sum_{k=1}^{n} k(k+1)= \frac{n(n+1)(n+2)}{3}$$ Help would be really appreciated.

Let's use your second example as a prototype for induction proofs.

base case: Usually, we check that the result holds for small values of $$n,$$ e.g., $$n = 0,$$ $$n = 1,$$ or $$n = 2,$$ but some induction proofs begin with larger values of $$n$$ than this. Considering that your sum begins with $$k = 1,$$ let's use $$n = 1$$ as our base case. We want to say that the left-hand side (LHS) and the right-hand side (RHS) are equal when $$n = 1.$$ Now, we have that $$\text{LHS} = 1(1 + 1) = 2$$ and $$\text{RHS} = \frac{1(1 + 1)(1 + 2)}{3} = \frac{(1)(2)(3)}{3} = 2.$$ We have verified the formula for $$n = 1,$$ so we can proceed.

inductive hypothesis: We have already established that the formula holds for $$n = 1,$$ so we will assume that the formula holds for some integer $$n \geq 2.$$ We want to verify the formula for $$n + 1.$$

proving the formula for $$n + 1$$: On the left-hand side, we have $$\sum_{k = 1}^{n + 1} k(k + 1) = (n + 1)(n + 1 + 1) + \sum_{k = 1}^n k(k + 1).$$ But by our inductive hypothesis, the sum on the right is $$\frac{n(n + 1)(n + 2)}{3},$$ hence we have that $$\text{LHS} = (n + 1)(n + 2) + \frac{n(n + 1)(n + 2)}{3} = \frac{3(n + 1)(n + 2)}{3} + \frac{n(n + 1)(n + 2)}{3} = \frac{(n + 1)(n + 2)(n + 3)}{3}.$$ But this is the same as the right-hand side since we have that $$\text{RHS} = \frac{(n + 1)(n + 1 + 1)(n + 1 + 2)}{3} = \frac{(n + 1)(n + 2)(n + 3)}{3}.$$

invoking induction: By the Principle of Mathematical Induction, we are done once we show

1.) $$P(n_0)$$ holds for small non-negative integers $$n_0$$ (e.g., $$n_0 = 0,$$ $$n_0 = 1,$$ or $$n_0 = 2$$) and

2.) $$P(n + 1)$$ holds whenever $$P(n)$$ holds for any integer $$n \geq n_0.$$

We have established both of these, so our proof by induction is complete.

• It is also a good idea when using induction to explicitly state at the beginning of the proof something along the lines of, "We proceed by induction." – Carlo May 30 at 17:31
• Thank you for the answer! so you used n instead of k in this example? – Katerina May 30 at 18:10
• No. Both $n$ and $k$ show up in the problem you asked about. When doing induction, you will induct on $n;$ observe that $k$ is simply the index of summation. – Carlo May 30 at 20:17

The general way that we do induction is show that if the $$n=k$$ is true, that the $$n=k+1$$ case must also be true. So in this example if we can show that $$(11^n-1)\mod 10 = 0 \implies (11^{n+1}-1)\mod 10 = 0$$ And then start with $$(11^0-1)\mod 10 = 0$$ , this implies that the $$11^1$$ case is true, which means the $$11^2$$ case is true, then $$11^3$$, ... And so on.

• Also, I'm not sure induction is the best method for your other problem. Learning about integer power sums, which Mathologer has a great video on would help you with this problem. – K.defaoite May 30 at 17:16
• I must do it by induction – Katerina May 30 at 17:17
• It turns out that the induction proof for the sum formula is quite straightforward. If you split the summand into $k$ and $k^2,$ you have to prove the sum formulas for those by (none other than) induction. – Carlo May 30 at 17:29