0

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.

Katerina
  • 3

2 Answers2

0

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.

K.defaoite
  • 12,536
  • 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 '20 at 17:16
  • I must do it by induction – Katerina May 30 '20 at 17:17
  • 1
    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. – Dylan C. Beck May 30 '20 at 17:29
0

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.

Dylan C. Beck
  • 4,811
  • 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." – Dylan C. Beck May 30 '20 at 17:31
  • Thank you for the answer! so you used n instead of k in this example? – Katerina May 30 '20 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. – Dylan C. Beck May 30 '20 at 20:17