0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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." $\endgroup$ – Carlo May 30 at 17:31
  • $\begingroup$ Thank you for the answer! so you used n instead of k in this example? $\endgroup$ – Katerina May 30 at 18:10
  • $\begingroup$ 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. $\endgroup$ – Carlo May 30 at 20:17
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – K.defaoite May 30 at 17:16
  • $\begingroup$ I must do it by induction $\endgroup$ – Katerina May 30 at 17:17
  • 1
    $\begingroup$ 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. $\endgroup$ – Carlo May 30 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.