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)
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
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?
(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 ?
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.