0

Homework problems I'm currently taking a discrete math class and was hoping for some tips to solve problems that are similar to the two in the image. I've already done problem ten, but it was quite troublesome even after I watched a couple of different videos.

This is about how I ran through it. I made sure it passed the initial n=1 test, which succeeded. After that, I sort of skipped around a little and swapped n for m+1 to do the final check, which gave me my answer. This is just my scuffed way of doing it and I'm not sure if its even right so.

Anyways, to sum it up, if anyone could make induction a bit simpler for me to understand I would be grateful.

False King
  • 3
  • 1

2 Answers2

1

As you can see from problem 10, the equation

$$\displaystyle \sum_{1 \leq k \leq n} k(k+1) = \frac{n(n+1)(n+2)}{3}$$

contains a variable $n$. So, it doesn't make sense to ask if the equation is true or not, right? However, it does make sense to ask whether or not the equation is true for specific values of $n$. The problem wants us to show that it's actually true for every $n = 1, 2, 3, ...$. For problems like these, induction is often useful to use.

You start with showing the base case. This is to show the equation, or statement, is true for some first value of your induction variable (in our case, the induction variable is $n$). From what you've said, it looks like you comfortable with that step already. Now the next step in induction proofs is usually called the inductive step. It's where you assume the equation, or statement, is true for some arbitrary positive whole number $n = m$, and then try to show that the equation would also be true for $n = m+1$. If you think about it for a second, those two steps combined would mean the equation is true for all $n = 1, 2, 3, ...$.

You may use any variable name instead of $m$ as you like, so long as it doesn't clash with other notation or cause potential confusion. In the process of trying to show that the equation is true for $n = m+1$, we may use our assumption that is was true for $n = m$. For our case, we would assume that the following is true

$$\displaystyle \sum_{1 \leq k \leq m} k(k+1) = \frac{m(m+1)(m+2)}{3}$$

Then, we would try to calculate $\displaystyle \sum_{1 \leq k \leq m+1} k(k+1)$ by using the fact that the equality above is true:

$\displaystyle \sum_{1 \leq k \leq m+1} k(k+1) \\ = \displaystyle \sum_{1 \leq k \leq m} k(k+1) + (m+1)((m+1)+1) \\ = \frac{m(m+1)(m+2)}{3} + (m+1)(m+2) \\ = \frac{m(m+1)(m+2)}{3} + \frac{3(m+1)(m+2)}{3} \\ = \frac{m(m+1)(m+2) + 3(m+1)(m+2)}{3} \\ = \frac{(m+1)(m+2)(m+3)}{3} $

But, this is exactly what we wanted it to be because, it means our original equation is true for $n = m+1$. Therefore, by induction,

$$\displaystyle \sum_{1 \leq k \leq n} k(k+1) = \frac{n(n+1)(n+2)}{3}$$

is true for all $n = 1, 2, 3, ...$.

Coreymonsta
  • 104
  • 1
    This was super helpful, I appreciate it a lot. Having my professor for the class have a heavy accent plus it being online has sort of left me clueless. I tried previously watching a few videos, but all of the problems they would work weren't really that similar to the ones I was working so I was stumped. – False King Sep 18 '20 at 07:19
  • Glad to have helped. Good luck! – Coreymonsta Sep 18 '20 at 07:22
1

  1. Identify the induction variable (not always "$n$", sometimes more than just a variable),

  2. Prove the base case (not always $n=1$),

  3. Prove that if the claim is true for $n$ (at least equal to $n$ in the base case), it is true for $n+1$.

Example (not from yours):

$$\sum_{1\le n\le m}n=\frac{m(m+1)}2.$$

  1. The induction variable is $m$.

  2. With $m=1$, $\displaystyle\sum_{1\le n\le 1}1=\dfrac{1(1+1)}2$ is true.

  3. Compare $$\sum_{1\le n\le m}n=\frac{m(m+1)}2$$ and $$\sum_{1\le n\le m+1}n=\frac{(m+1)(m+2)}2.$$ The second sum has an extra term, $m+1$ and it is true that $$\frac{m(m+1)}2+m+1=\frac{(m+1)(m+2)}2.$$

As the property was shown to be true for $n=1$, by 3. it is also true for $2$, then $3,4,\cdots$

Other example:

$$2^n>n^2.$$

  1. The induction is on $n$.

  2. $2^1>1^2$.

  3. Compare $2^n>n^2$ and $2^{n+1}>(n+1)^2$. The latter can be written $2\cdot2^n>(n+1)^2$. So by the induction hypothesis we can write $$2\cdot2^n>2n^2.$$ Then $$2n^2\ge(n+1)^2.$$ provided that $$\sqrt2\ge\dfrac{n+1}{n},$$ which is true as of $n=3$.

Now observe that we proved for $n=1$, but induction only works for $n\ge3$ and we need to adjust the base case. In fact, the property fails for $n=2,3,4$, and $$2^5>5^2$$ is our base case.