Tower of Hanoi confusion from Concrete Mathematics

Question

so I just started reading Concrete Mathematics as a precursor to The Art of Computer Programming vol. 1. I'm on page 3 and I'm already struggling. Anyway, the recurrence is stated to be:

$2T_{n-1} +1$

But I don't understand how this works. If $n$ is 3, then we would have:

$2T_{3-1}+1$

or

$2(2) + 1 = 4$

correct? But that's not right. The answer here is 7. They go on to compute it saying:

$T_3 = 2 * 3 + 1 = 7; T_4 = 2*7+1=15$

Now the $T_4$ one makes a little bit of sense if you calculate $2*4 - 1$ instead of $2*(4-1)$, but that logic doesn't seem to apply to that one. I'm trying to figure out of it's a range of $n$ to $1$, but $2*(3*2*1) + 1 = 13$ so obviously that's not right...

Oh, maybe I've got it. I'm substituting $2T_{n-1}$ with $2(n-3)$ when I'm actually supposed to use the result of $T_{n-1}$ instead and multiply that by 2 and add 1.

Thanks in advance.

Yeah, $2T_{3-1}+1$ simplifies to $2T_2+1$, so you have to plug in a value of $T_2$ to evaluate it. — G Tony Jacobs, Jul 24 '17 at 02:27
That's kind of the point of a "recurrence". If you're not subbing in the previous value, you're not doing a recurrence. — G Tony Jacobs, Jul 24 '17 at 02:28
That makes sense, I wasn't making the connection that's what an induction is about. I haven't taken a math class in about 3 years(Calculus) and I failed it. — Cory Madden, Jul 24 '17 at 02:30

score 5 · Accepted Answer · answered Jul 24 '17 at 02:28

5

Hint:

$T_1=\color{#C00}{1}$
$T_2=2T_1+1=2\cdot\color{#C00}{1}+1=\color{#090}{3}$
$T_3=2T_2+1=2\cdot\color{#090}{3}+1=\color{#00F}{7}$
$T_4=2T_3+1=2\cdot\color{#00F}{7}+1=15$

answered Jul 24 '17 at 02:28

robjohn

345,667

Thanks, @robjohn. I'll come back and accept your answer in 8 minutes when it allows me to. – Cory Madden Jul 24 '17 at 02:30

Tower of Hanoi confusion from Concrete Mathematics

1 Answers1