Towers of hanoi induction- slight bit i don't understand

[pyrosilver]

Towers of hanoi induction-- slight bit i don't understand

Homework Statement

I am trying to prove towers of hanoi. Now I am on the induction part and there is a part I don't get. I have the whole thing, but i don't understand a couple lines.

Homework Equations

The Attempt at a Solution

WTS: f(n+1) = 2ⁿ⁺¹ - 1
By the Induction Hypothesis, f(n) = 2^n-1.

Earlier, we showed f(n) = f(n-1) + 1 + f(n-1).

By the recursive definition,
f(n+1) = f(n) + 1 + f(n).
f(n+1) = 2f(n) + 1
f(n+1) = 2(2^n-1) + 1
f(n+1) = 2(2ⁿ - 2) + 1
f(n+1) = 2ⁿ⁺¹ - 1.
QED.

Ok I get the first line...get the second line...I get that you substitute f(n) in the third line... but I have no idea what the fourth and fifth lines are about! Please help me? I need to understand this by tomorrow :(

 

[emyt]

Homework Statement

I am trying to prove towers of hanoi. Now I am on the induction part and there is a part I don't get. I have the whole thing, but i don't understand a couple lines.

Homework Equations

The Attempt at a Solution

WTS: f(n+1) = 2ⁿ⁺¹ - 1
By the Induction Hypothesis, f(n) = 2^n-1.

Earlier, we showed f(n) = f(n-1) + 1 + f(n-1).

By the recursive definition,
f(n+1) = f(n) + 1 + f(n).
f(n+1) = 2f(n) + 1
f(n+1) = 2(2^n-1) + 1
f(n+1) = 2(2ⁿ - 2) + 1
f(n+1) = 2ⁿ⁺¹ - 1.
QED.

Ok I get the first line...get the second line...I get that you substitute f(n) in the third line... but I have no idea what the fourth and fifth lines are about! Please help me? I need to understand this by tomorrow :(

I believe that the induction hypothesis should be (2^n) - 1, it should be clear after fixing that up

 

[pyrosilver]

Oh okay, i missed that, thanks. I'm still confused though...so the third line would be

f(n+1) = 2(2ⁿ - 1) + 1, right? why is the next line 2(2ⁿ - 2) + 1?

 

[emyt]

after 2(2^n - 1) , you should get (2^n+1 - 2) + 1 --> 2^n+1 - 1 and it is proven.

you have some more typo errors, that line should be 2(2^n - 1) + 1, since you had above that 2f(n) + 1 - which now after clearing up, is definitely 2(2^n - 1) + 1

 

[pyrosilver]

OHHH sorry that took me awhile! Thank you so much lol xD

I have another question on a diff topic? I feel really stupid for asking but I'm not sure what to do.

for proving this carefully:

|x-3| = 8

I know you have to split it into two cases, x-3> 0. x-3 < 0.

For x-3>0,
x-3 = 8
x= 11.

For x-3<0, what do I do? I know it equals -5, but i don't know how to prove it?

 

[emyt]

OHHH sorry that took me awhile! Thank you so much lol xD

I have another question on a diff topic? I feel really stupid for asking but I'm not sure what to do.

for proving this carefully:

|x-3| = 8

I know you have to split it into two cases, x-3> 0. x-3 < 0.

For x-3>0,
x-3 = 8
x= 11.

For x-3<0, what do I do? I know it equals -5, but i don't know how to prove it?

Hi, the absolute function is explicitly defined, so just distinguish the cases where f(x) = x when x > 0 and -x when x < 0; when x> 3 x-3 , when x < 3 -(x-3) or 3-x

 

[HallsofIvy]

|x| is equal to x if $x\ge 0$, -x if x< 0.

So |x-3| is equal to x-3 if $x\ge 3$, -(x-3)= -x+ 3 if x< 3.

If $x\ge 3$ then |x- 3| becomes x- 3= 8 or x= 8+ 3= 11, which is, in fact, greater than 3. If x< 3 then |x- 3|= -(x-3)= -x+ 3= 8 so -x= 8- 3= 5 and x= -5, which is, in fact, less than 3. (You should always check to see if the result is in the correct range.)

x= 11 and x= -5 satisfy this equation. If x= 11, then x- 3= 11-3= 8 so |x- 3|= 8. If x= -5, x- 3= -5- 3= -8 so |-8|= 8.