Induction for inequality: 2^{|x| - 1} <= x <= 2^{|x|}

[ReallyBadAtMathGuy]

We have to prove this inequality by induction for x > 0. Additionally, we have to conclude that |x| = ⌊log2 x⌋ + 1. I am struggling with the induction step as I don't know what to do

base case: x = 1

2^{|1| - 1} ≤ 1 < 2 ^|1| → 1 ≤ 1 < 2

induction step: x → x + 1

2^{|x+1| - 1} ≤ x + 1 < 2^{|x + 1|}

→ 2^|x| ≤ x + 1 < 2^{|x| + 1}

Thanks for any help

 

[stapel]

View attachment 36754

We have to prove this inequality by induction for x > 0. Additionally, we have to conclude that |x| = ⌊log2 x⌋ + 1. I am struggling with the induction step as I don't know what to do

base case: x = 1

2^{|1| - 1} ≤ 1 < 2 ^|1| → 1 ≤ 1 < 2

induction step: x → x + 1

2^{|x+1| - 1} ≤ x + 1 < 2^{|x + 1|}

→ 2^|x| ≤ x + 1 < 2^{|x| + 1}

Thanks for any help

The steps are (a) the base step, (b) the assumption step, and (c) the induction step. But I'm not seeing your assumption step?

 

[blamocur]

This inequality is not true: it fails starting with x = 2. No wonder you can't get the induction step.

 

[Dr.Peterson]

View attachment 36754

We have to prove this inequality by induction for x > 0. Additionally, we have to conclude that |x| = ⌊log2 x⌋ + 1.

The conclusion is false, too!

And it's also odd that they take the absolute value of a variable that is promised to be positive -- but they don't take the absolute value in the conclusion, where it has to be positive because they take the log!

Looking again at the conclusion, I suspect they are using a special definition of |x|, probably the number of digits in the binary expansion. For example, 5 = 101₂, with 3 digits, and log₂(5) = 2.322; rounding that down and adding 1, you get 3.

Check your source carefully, and show us everything it says.

 

[ReallyBadAtMathGuy]

The steps are (a) the base step, (b) the assumption step, and (c) the induction step. But I'm not seeing your assumption step?

Oh yeah sorry, the assumption step is:
for any x>0

 

[ReallyBadAtMathGuy]

The conclusion is false, too!

And it's also odd that they take the absolute value of a variable that is promised to be positive -- but they don't take the absolute value in the conclusion, where it has to be positive because they take the log!

Looking again at the conclusion, I suspect they are using a special definition of |x|, probably the number of digits in the binary expansion. For example, 5 = 101₂, with 3 digits, and log₂(5) = 2.322; rounding that down and adding 1, you get 3.

Check your source carefully, and show us everything it says.

It is as you said. |x| is the number of digits in the binary expansion. I forgot to mention that. Thanks for mentioning it

 

[ReallyBadAtMathGuy]

View attachment 36754

We have to prove this inequality by induction for x > 0. Additionally, we have to conclude that |x| = ⌊log2 x⌋ + 1. I am struggling with the induction step as I don't know what to do

base case: x = 1

2^{|1| - 1} ≤ 1 < 2 ^|1| → 1 ≤ 1 < 2

induction step: x → x + 1

2^{|x+1| - 1} ≤ x + 1 < 2^{|x + 1|}

→ 2^|x| ≤ x + 1 < 2^{|x| + 1}

Thanks for any help

|x| = number of digits in binary, for example |5| = 3 since 5₁₀ = 101₂

 

[Dr.Peterson]

It is as you said. |x| is the number of digits in the binary expansion. I forgot to mention that. Thanks for mentioning it

Now try the induction, using that information!

I haven't tried it myself, but I would not be surprised if the induction is not on x, but on, say, |x|.

Note that the work you showed is nonsense given this definition, so we haven't yet seen any proper work from you.

Oh yeah sorry, the assumption step is:
View attachment 36756 for any x>0

No, you can't just assume that! That's what you're trying to prove.

Please give us more context. You claim to be Bad At Math, but clearly you are in a fairly advanced course. What are you learning? Has anything been said, or any examples been given, that might suggest tricks you could use?