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
∑k = n(n+1)/2
∀(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"
"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)