Simple proof by induction problems

Question

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.

Answer 1

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.

Answer 2

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.