Proof by induction that recursive function $\text{take}$ satisfies $\text{take}(n) = 100 - 2n$

Question

I'm sick and tired off posting threads about induction... I just can't seem to get it, I need someone to give me a detailed explanation and treat me like a 5 year old, literally. I'm wasting a lot of time trying to revise one topic, and getting nowhere... I just don't understand :O

Here's an attempt :

Base case take(0) = 100 - (2*0) = 100 therefore it holds

Assume n=k holds take(k) = 100-(2*k)

prove take(k+1) = 100-(2*k+1)

take(k+1) = take(k)100-2k+1 take(k+2) = ...

Answer 1

PARENTHESIS!

You want to prove

${\rm take}(n)=100-2n$

for the special case when $n=k+1$. So, substitute $k+1$ in place of the $n$, but not only formally, it is a separate unit, needs parenthesis:

${\rm take}(k+1)=100-2(k+1)$

Then open the parenthesis, so what you have to prove is

${\rm take}(k+1)=100-2k-2$

and you're there soon..

Answer 2

You did not substitute correctly in what you want to prove. It should be take $(k+1)=100-2(k+1)$.

Your proof should then start take(k+1)=take(k)-2 and plug in your assumption for take(k)

Answer 3

(I'm going to say the same thing over and over again in what I hope are slightly different ways. So see if you can understand any of them, you don't need to understand all of them.)

Induction is a domino chain. The base case is when you tip the first domino. The inductive step is when you set up the dominos, you want the next domino to be close enough to the previous one, so that when the "previous" one falls, the "next" one will too.

Written with symbols, if $S(n)$ is a sentence with one variable $n$, (i.e. in your example you have $S(n)=$ "take$(n)$ is equal to take$(n-1)$ minus $2$.") then to prove $S(n)$ is true for all $n$, you need

• $S(0)$ to be true
• $S(k+1)$ to be true under the assumption that $S(k)$ is known to be true.

The second point is sticky. You are not proving that $S(k)$ is true. You assume it is true. What you are proving is that $S(k+1)$ is also true.

When I was learning induction, this always felt like a very stupid thing to do. I thought: well, if you know that $S(k)$ is true for all $k$ then you obviously already know it's true for $k+1$. And in fact, this is true. But this is not what induction is, because in induction you are never given that $S(k)$ is true for every $k$. Rather, you only ever know that $S(n)$ is true for a single value of $n$: we name that value $k$.

This is why you seemingly randomly change from $n$ to $k$. I always thought this was stupid too, but this is the reason. As a computer scientist this should probably make more sense to you than it did to me: we want to think of $n$ as a variable, but $k$ is supposed to be one specific value of the variable. But of course if $k$ was an actual number like 500 then we couldn't prove very much, so we have to give it a letter name. Now it "looks" like a variable on paper, but never be fooled: it is a value.

Base cases are usually easy. In your particular example, it is easy to see that take$(0)$ is indeed $100-(2\cdot 0)=100$.

Now for the inductive step you play this game:

I say "Here is a number $k$. I am telling you, $S(k)$ is true."

You say "Why?"

I say "Trust me."

You say "Why?"

We do this for a while until you finally agree to trust me. Maybe I stole the knowledge from the French government, or something, I don't know.

Then I say "Tell me, is $S(k+1)$ also true?"

You think for a while. Maybe you ask "Is $S(k-1)$ true?"

I say "Sorry, I don't know."

Maybe you ask "Is $S(2)$ true?"

I say "Sorry, I only know that $S(k)$ is true. And I guess you already told me that $S(1)$ was true, so I know that too."

Of course, if I actually gave you a number, like 500, and I said $S(500)$ is true, then you could brute force it. But the point is, I might give you any number, and the goal of the inductive proof is to be prepared regardless of which number $k$ I give you.

Okay, so let's turn to your specific example.

I say "Here is a number $k$. I am telling you, take$(k)$ is $100-2k$"

[…]

Then I say "Tell me, is it true that take$(k+1)=100-2(k-1)$ ?".

So you look at what you know about take$(k+1)$. Well, your definition tells you that for variable $n$ you have $$\text{take}(n)= \text{ take}(n-1)-2.$$ Since $n$ is truly a variable, you can replace it with $k+1$, which is a value. Then you have $$\text{take}(k+1)= \text{ take}(k+1-1)-2 = \text{ take}(k)-2.$$

This is good news! Why? Because I already told you what take$(k)$ is. That was the whole point of using $k$ instead of some other value.

Now, you can finish from here. You want to know take$(k+1)$. You have a relation between take$(k+1)$ and take$(k)$, and you have take$(k)$. Combine these thigns you have for great victory.

---

Final thoughts: Induction problems often to feature odd algebra, which leads some people to think they are bad at induction, when really they just have weak algebra skills. As a loose test, if you understood everything up to your specific example without difficulty, then your problem was probably not induction, it was algebra.