# Thread: Proof by induction, 2^k-1 +1 = k+1

1. ## Proof by induction, 2^k-1 +1 = k+1

Hey I've come across a question which is a little weird to prove by induction.

This is the function,
"Let T be a total function from Z+ to R+ such that T is nondecreasing on Z+, such that T(1) =1 and:

for any positive real number k, T(2k) = T(2k-1)+1"

I have to prove that for any Natural number T(2k) = k+1 by induction.

A few questions I had to do with this function was find T(2), T(4) and T(8) (You'll notice they're all powers of 2)

Example, to find T(2):

2 = 21So, k = 1
T(21) = T(21-1) +1 (Second part of equation from the function definition)

T(21-1) = T(20) = T(1) (The next number is the power before it, + 1)

Given; T(1) =1
T(1) + 1 = 2, therefore T(2) = 2

You use the same method to find:
T(4) = 3
T(8) = 5
You could keep going:
T(16) = 9
T(32) = 17
...

Back to my main question, how do I prove that for any Natural number k T(2k) = k + 1
This is what I have so far:

Let P(k) be the statement : T(2k) = k + 1
Let k = 1 (basis step)
P(1) = T(2) = k +1
... show work etc <--- for this part do I have to state somewhere that T(1) is given in order to get T(2)??
2 = 2
Therefore P(1) is true because T(2) = 1 + 1
Let n be an arbitrary element of N (natural numbers) and assume P(n) (inductive step)

This part is where i'm stuck, we are given several definitions/properties that we are encouraged to use to solve this problem, these are the relevant ones:

∀n∈Z+, ∃k∈Z+, 2k−1≤n≤2k

∀n∈Z+,
n
∑k = n(n+1)/2
k=1

∀(a,b)∈R+2, log(ab) = log(a)+log(b)
∀a∈R+, ∀k∈N, log(ak) = k log(a)
log(1) = 0
log is increasing on R+
∀a∈R+, log2(a) = log(a)/log(2)

Any help on the inductive step would be appreciated.

I also cannot figure out a few other questions with the same function:
"Show that for any positive integer n we have T(n) <= log2(2n)+1"
and
"Show that T(n) is O(log(n))" (Yes that's big O notation for those computer scientists, which really is asking, show that There exists an integer M that you can multiply f(x) such that f(x) <= M*g(x) where f and g are two functions defined on subsets of R)

2. ## Re: Proof by induction, 2^k-1 +1 = k+1

Originally Posted by bulletmagnet1234
T(1) =1 and:

for any positive real number k, T(2k) = T(2k-1)+1"

I have to prove that for any Natural number T(2k) = k+1 by induction.
Originally Posted by bulletmagnet1234
T(8) = 5
How did you find this?

Originally Posted by bulletmagnet1234
You could keep going:
T(16) = 9
T(32) = 17
...

Back to my main question, how do I prove that for any Natural number k T(2k) = k + 1
This is what I have so far:
It's strange that you are trying to prove something that you determined is false. If T(32) = T(2⁵) = 17, then T(2k) = k+1 can't be true.

3. ## Re: Proof by induction, 2^k-1 +1 = k+1

Originally Posted by emakarov
How did you find this?
T(1) = 1 is given in the question. That's why it's in quotation marks with the preceding statement, it's a definition.
T(8) = 5 because when it's T(8), k = 3 (2^3=8) and this is equal to T(2^(k-1))+1" which is 4+1

Originally Posted by emakarov
If T(32) = T(2⁵) = 17, then T(2^k) = k+1 can't be true.
However it is true for T(1) and T(2)

T(1) = 1 = 0 + 1, k=0
T(2) = 2 = 1+1, k=1

I don't know if that somehow helps?
The next number is the power before it, + 1

I know there is a solution otherwise my teacher wouldn't have given it to us.
Are you suggesting there is no algebraic way to manipulate T(2^k) = k + 1 in this problem to prove T(2^n) = n + 1 or T(2^(n+1)) = (n+1) + 1.
Perhaps I am approaching this problem incorrectly?

4. ## Re: Proof by induction, 2^k-1 +1 = k+1

Originally Posted by bulletmagnet1234
T(4) = 3
Originally Posted by bulletmagnet1234
T(8) = 5 because when it's T(8), k = 3 (2^3=8) and this is equal to T(2^(k-1))+1" which is 4+1
It seems you are computing T(k) as if it were $\displaystyle 2^{k-1}+1$. Instead, it's $\displaystyle T(2^{k-1})+1$. If n is a power of 2, then $\displaystyle T(n)=T(n/2)+1$. You found that T(4) = 3, so T(8) = T(4) + 1 = 4.

5. ## Re: Proof by induction, 2^k-1 +1 = k+1

Originally Posted by emakarov
You found that T(4) = 3, so T(8) = T(4) + 1 = 4.
I know what you just wrote is correct and what I wrote was wrong, but I don't fully understand why I am wrong or simply how to interpret the function definition.
(How I know you are right is my colleagues went a similar way to get the answer but I didn't understand it so I tried to do it on my own, a different way, but I can't contact them right now for help)
Could someone help me understand the question better? And what the function T really is?

Also if we go through it this way, does that mean we can prove by induction T(2^k) = k + 1 ?

6. ## Re: Proof by induction, 2^k-1 +1 = k+1

Originally Posted by bulletmagnet1234
Could someone help me understand the question better? And what the function T really is?
In computer science parlance, function T is defined recursively, and I believe that recursion is one of the hardest things to grok. In math, such functions are called recurrence relations. You compute their values one by one. To compute the next value, you need the previous one. In a typical recurrence relation F, F(k + 1) depends not only on k, but also (or exclusively) on F(k). (One could say that ultimately F does depend only on k, but to compute F(k + 1) there may not be a simpler way than to compute F(0), ..., F(k) and then use F(k).)

As an exercise, you could compute F(k) for small values of k when F is defined as follows:

(1) F(0) = 0, F(k + 1) = F(k) + 1
(2) F(0) = 1, F(k + 1) = 2F(k)

In your problem, if we consider the recurrence relation T(2k) = T(2k-1) + 1 for integer k only, it defines T only for powers of 2, i.e., we can use it to compute T(2), T(4), T(8), T(16) and so on. But the idea is the same: we need to actually use T(8) and not just 4 (since 2⁴ = 16) to compute T(16). The recurrence relation says that we need to add 1 to T(8) to get T(16). Similarly, we add 1 to T(4) to get T(8). Since T(4) = 3, T(8) = T(4) + 1 = 3 + 1 = 4, and T(16) = T(8) + 1 = 4 + 1 = 5.

Originally Posted by bulletmagnet1234
Also if we go through it this way, does that mean we can prove by induction T(2^k) = k + 1 ?
Yes.