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(2^{k}) = T(2^{k-1})+1"

I have to prove that for anyNaturalnumber T(2^{k}) = 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 = 2^{1}So, k = 1

T(2^{1}) = T(2^{1-1}) +1 (Second part of equation from the function definition)

T(2^{1-1}) = T(2^{0}) = 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 anyNaturalnumber k T(2^{k}) = k + 1

This is what I have so far:

Let P(k) be the statement : T(2^{k}) = 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(a^{k}) = 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) <= log_{2}(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)