In this video, we're going to talk about a proof by mathematical induction and we're going to critique it. We're going to try to identify some of the mistakes that are made in this proof.
This proof at some point was a midterm question and most of these mistakes are ones that I found on papers from students. So here's our problem:
Use mathematical induction to prove $\displaystyle \sum_{i=1}^n \frac{i}{3^i} =\frac{3}{4}-\frac{2n+3}{4 \cdot 3^n}$ for all natural numbers $n$
Proof: We prove $P(n)$ is true for all natural numbers $n$ by induction
Base Case: When $i=1$,
$$\sum_{i=1}^1 \frac{i}{3^i}=\frac{3}{4}-\frac{2(1)+3}{4\cdot 3^1}=\frac{3}{4}-\frac{5}{12} =\frac{9}{12}-\frac{5}{12}=\frac{4}{12}=\frac{1}{3}$$Induction Hypothesis: Assume $P(k)$ is true for all natural numbers $1\leq i \leq k$, $k \geq 2$. That is, assume that
$$P(k)=\sum_{i=1}^k \frac{k}{3^k}=\frac{3}{4}-\frac{2k+3}{4\cdot 3^k}$$Induction Conclusion: For $P(k+1)$,
$$\begin{align} \sum_{i=1}^{k+1} \frac{i}{3^i}&=\sum_{i=1}^k \frac{i}{3^i}+\frac{k+1}{3^{k+1}}\\ &=\frac{3}{4}-\frac{2k+3}{4\cdot 3^k}+\frac{k+1}{3^{k+1}}\\ &=\frac{3}{4}-\frac{6k+9}{4\cdot 3^{k+1}}+\frac{4k+4}{3^{k+1}}\\ &=\frac{3}{4}-\frac{6k+9+4k+4}{4\cdot 3^{k+1}}\\ &=\frac{3}{4}-\frac{10k+13}{4\cdot 3^{k+1}}\\ &=\frac{3}{4}-\frac{2(k+1)+3}{4\cdot 3^{k+1}} \end{align}$$Therefore $P(k+1)$ is true.
If you haven't done so I would suggest taking a minute and actually trying to see how many of the errors that you can find in this proof.
So first, we start off with the proof. "We prove $P(n)$ is true for all natural numbers $n$ by induction".
Well one thing that we haven't done yet is we haven't identified what $P(n)$ is yet. You should state what the $P(n)$ that you're trying to prove is. I know that here it might seem very clear but even still, for proper writing technique, you should tell the reader what $P(n)$ is. You shouldn't introduce variables without letting the reader know what they are. So even straight out the gate we're off to a bad start.
"The base case when $i=1$" well that's not true, right? I mean the base case really is when $n=1$. $i$ is just the indexing variable that has nothing to do with the statement that we're trying to prove. I could have called $i$ something else and nothing would have really changed as long as I made sure that the other instances of $i$ matched it. So that's a problem. So this needs to be an $n$ instead of an $i$.
Now in line $1$, we're already up to $2$ mistakes and we're only on line $2$, line $1$, what do we have? Well we have $\displaystyle\sum_{i=1}^1 \frac{i}{3^i}$, that's okay. But then now we say $\displaystyle\sum_{i=1}^1 \frac{i}{3^i=\frac{3}{4}-\frac{2(1)+3}{4\cdot 3^1}$ but that is what we wanted to prove.
This $=$ is the statement when $n=1$ is plugged in. So this $=$ isn't really what we want. We want to show that this thing, after we do a whole bunch of work and get it down to $\displaystyle\frac{1}{3}$, is actually equal to the sum. This equal sign is actually a mistake. Right? We should just start with the sum, get down to $\displaystyle\frac{1}{3}$ and then claim that $\displaystyle\frac{1}{3}=\frac{3}{4}-\frac{2(1)+3}{4\cdot 3^1}$, which is true. So another mistake there.
The induction hypothesis, there are several mistakes here so let's talk about this.
"Assume $P(k)$ is true for all natural numbers $1\leq i\leq k$,$k \geq 2$." Okay, lots of mistakes. For one, $i$ is the indexing variable right, so we definitely don't want to say this.
This $1\leq i\leq k$, this doesn't make any sense. $i$ is the indexing variable of my summation. It has nothing to do with the induction hypothesis.
The next thing: the person wrote, "for all natural numbers". Well you don't want to assume that $P(k)$ is true for all natural numbers, that doesn't make any sense, right? You're trying to prove that $P(n)$ is true for all natural numbers so assuming that $P(k)$ is true for all natural numbers $k$ means that you're assuming what you want to prove is true.
What you really want to do is take one instance. So for some value of $k$, you want to assume that $P(k)$ is true and because that value is arbitrary, that's where the induction sort of makes sense. You take an arbitrary value to show that $P(k)\Rightarrow P(k+1)$ and because that $k$ was arbitrary, you can prove that $P(n)$ must always be true by the Principle of Mathematical Induction. Remember that's the idea, right?
Third mistake is we have $k\geq 2$, so even if you had written for some natural number $k$ with $k\geq 2$, we're still wrong. Why is that now?
The reason why were wrong now is because the smallest case in the induction hypothesis should overlap with the largest base case in your base cases. This is true for strong induction, this is true for just regular inductions as well.
So again, what's happening here? Well you have $k\geq 2$ and what this is sort of saying is that if you ended up proving that this was true, you would have proved that $P(2)\Rightarrow P(3)\Rightarrow P(4)\Rightarrow P(5)$, where $P$ is your statement of course, and so on and so forth.
That's what you've proved, but you haven't actually proved that $P(2)$ is true; so in some sense, you have this long, long string of implications, but you don't know that the first one is true so you don't know that all the other ones are true.
And again, if you think about it like a domino analogy, right, you know that the second domino will knock down the third one, and the third one will knock down the fourth one, and the fourth one will knock down the fifth one and so on and so forth, but you don't know that the second domino falls down.
This is why you need that overlap, right? If you say here instead $k \geq 1$ and then go through the proof and prove it, you proved that if $P(1)$ falls, then $P(2)$ falls, if $P(2)$ falls then $P(3)$ falls, and if $P(3)$ falls then $P(4)$ falls and so on and so forth. And we know that $P(1)$ falls because that was our base case. The combination of all of these things gives you the proof that you want.
All that being said, let's see if the next line is right: "That is, assume…" well we're off to a bad start again. "$P(k)=$" well $P(k)$ is a statement, so $P(k)$ can't equal a value which is what this says, so this $=$ sign doesn't make any sense. This $P(k)$ probably just shouldn't be here at all in the induction hypothesis.
Now we have $\displaystyle\sum_{i=1}^k \frac{k}{3^k}$ but for some reason we've also substituted the $k$ in for the index variable $i$, that's not right. Remember the index variable depends on the index on the bottom of the sum. It doesn't depend on the index at the top it just depends on the one at the bottom.
So when you're replacing the one, you're replacing the $n$ in the index variable in the statement, you really do want just the $n$ to become a $k$ and you want to leave the $i$'s alone because the $i$'s belong to the index variable in your summation notation. The right-hand side is correct so we did one out of three things correct there.
The induction conclusion: so for $P(k+1)$ what do we have? So this is actually a reasonable start to our proof. We start with the left-hand side of the thing we're trying to prove, but instead of $n$ we have a $k+1$, and now we're trying to go through and get to the end. So this is actually okay.
Some people probably leave the $n$ on the top of the sum and that's technically wrong you really do want $k+1$ here. Unless you tell the reader that you're making $n=k+1$ but I wouldn't do it like that, I would do it like this. So that's okay.
We've broken off the last term and it looks like we've done it correctly. You're taking $\displaystyle\sum_{i=1}^k \frac{i}{3^i}$, you leave that alone, and now you're plugging in the last term $\displaystyle\frac{k+1}{3^{k+1}}$.
Line $2$ this is a line that you really should explain. This is not immediately clear. What's happening here though is that you're using the induction hypothesis. You really should tell the reader "Hey I'm using the induction hypothesis at this point".
Line $3$ we attempted to find a common denominator but we've left the denominator on the right the same. So we really should have $4\cdot 3^{k+1}$ on that fraction, that's a mistake.
Here's another mistake that a lot of people made. We're taking $\displaystyle\frac{3}{4}-\frac{6k+9}{4\cdot 3^{k+1}}$. Really, this negative goes to both of the terms in the numerator. So it looks like:
$$-\frac{6k+9}{4\cdot 3^{k+1}}=\frac{-6k-9}{4\cdot 3^{k+1}}$$In line $5$, you've just written the sum of the things on the top however $6k$ and $9$ should have been negative from the negative out front. When you write the fraction like $\displaystyle-\frac{6k+9+4k+4}{4\cdot 3^{k+1}}$, the negative is actually going to all four terms.
So now you're going get, you know, you're going get $-10k-13$ as opposed to $-6k-9+4k+4=-2k-5$. This is a very bad mistake to make. Remember that when you're doing this, you really want to bring the negative in first and then add the numerators.
The final line we've clearly cheated. There's no way to make $-(10k+13)$ look like $-(2(k+1)+3)$. Don't cheat like this, it's very obvious that there's steps missing.
"Therefore $P(k+1)$ is true." It's good that you have a start of a concluding statement but we're not done yet. Why can we conclude, therefore, that $P(n)$ is true for all natural numbers $n$? That's because of the Principle of Mathematical Induction. So we really should have a full concluding statement that says, “therefore $P(n)$ is true for all natural numbers $n$ by the Principle of Mathematical Induction."
I think I found all mistakes in this proof. At least all the ones I intentionally made, I found. Now, let's try to write this up a little bit better, a little bit cleaner, a little bit nicer.
By the way, grading this would be very difficult because realistically no step is correct. Everything looks like it's good, but your base case has errors, your statement at the beginning is unclear, your induction hypothesis is a disaster, your induction conclusion has right elements like you broke it up but I mean other than that, much of this is incorrect in terms of manipulations, and you don't have a concluding statement.
This would be a tough proof to mark and giving it $0$ would probably not be that unreasonable despite the fact that many of the ideas that you need are here.
Let's go to an actual proof. Okay, so same question. I'm going to try to give you a proof that I've written. Hopefully it's correct, we'll see.
Use mathematical induction to prove $\displaystyle \sum_{i=1}^n \frac{i}{3^i} =\frac{3}{4}-\frac{2n+3}{4 \cdot 3^n}$ for all natural numbers $n$
Proof: Let $P(n)$ be the statement $\displaystyle \sum_{i=1}^n \frac{i}{3^i} =\frac{3}{4}-\frac{2n+3}{4 \cdot 3^n}$. We prove that this statement is true for all natural numbers $n$ by induction
Base Case: When $n=1$,
$$\text{RHS}=\frac{3}{4}-\frac{2(1)+3}{4\cdot 3^1}=\frac{3}{4}-\frac{5}{12} =\frac{9}{12}-\frac{5}{12}=\frac{4}{12}=\frac{1}{3}=\sum_{i=1}^1 \frac{i}{3^i}=\text{LHS}$$Therefore $P(1)$ is true.
I have a right- hand side and a left-hand side proof and I'm starting with the right hand side. Notice, by the way, in this case this statement is true. The right hand side is equal to $\displaystyle\frac{3}{4}-\frac{2(1)+3}{4\cdot 3^1}$, and each subsequent difference of fractions is just simplification.
I've started with the right-hand side and gotten to the left-hand side. That is a complete and valid proof.
Induction Hypothesis: Assume $P(k)$ is true for some integer $k \geq 1$. That is, assume that
$$\sum_{i=1}^k \frac{i}{3^i}=\frac{3}{4}-\frac{2k+3}{4\cdot 3^k}$$Now my induction hypothesis, I've written it out a little bit different than I probably normally would there's a reason why. "Assume $P(k)$ is true for some integer…" remember we're only assuming that this is true for a single case. A lot of students wrote "for some natural numbers", "for some integers”, no, it's really just for some single integer $k \geq 1$.
Can you write just for some natural number $k$? You absolutely can, but I wanted to make it clear that $k\geq 1$, and why the $1$ here? Because the last base case we proved was $n=1$. You want that overlap for the same reason that we talked about earlier.
Induction Conclusion: We now prove that $P(k+1)$ is true, that is, we prove that
$$\sum_{i=1}^{k+1} \frac{i}{3^i}=\frac{3}{4}-\frac{2(k+1)+3}{4\cdot 3^{k+1}}$$This is the statement that we want to prove. It's very clear what we want to prove, and now I'm going take the left hand side and derive the right hand side, which is what I say next.
Now, beginning with the left hand side yields
$$\begin{align*} \sum_{i=1}^{k+1} \frac{i}{3^i}&=\sum_{i=1}^k \frac{i}{3^i}+\frac{k+1}{3^{k+1}}\\ &=\frac{3}{4}-\frac{2k+3}{4\cdot 3^k}+\frac{k+1}{3^{k+1}}&&\text{By the Induction Hypothesis}\\ &=\frac{3}{4}+\frac{-6k-9}{4\cdot 3^{k+1}}+\frac{4k+4}{4\cdot 3^{k+1}}\\ &=\frac{3}{4}+\frac{-6k-9+4k+4}{4\cdot 3^{k+1}}\\ &=\frac{3}{4}+\frac{-2k-5}{4\cdot 3^{k+1}}\\ &=\frac{3}{4}+\frac{-2k-2-3}{4\cdot 3^{k+1}}\\ &=\frac{3}{4}-\frac{2k+2+3}{4\cdot 3^{k+1}}\\ &=\frac{3}{4}+\frac{2(k+1)+3}{4\cdot 3^{k+1}} \end{align*}$$Therefore $P(k+1)$ is true. Thus, by the Principle of Mathematical Induction, $P(n)$ is true for all natural numbers $n$.$\quad\blacksquare$
That's it, this is a complete proof. I think it is correct and worth full marks and everything is good.
But that is it. So hopefully, I've given you a little bit of insight as to some common mistakes that people make when writing an induction proof, and hopefully this helps you to frame future induction proofs properly.
One final piece of advice: again, whenever a student comes to me and says that they're stuck with an induction proof, one of the first things I ask them is, "Well did you write down the statement $P(n)$?" and many of the times students will tell me, "No I haven't" and I find that just the act of writing the statement down often gives students a really big push as to how to start your induction proofs and how to frame it properly and how to finish it off.
So if I can give you one piece of advice with an induction proof that would be the piece I'd give you. Write down $P(n)$ explicitly. Thank you very much, hopefully this helped.