Proof By Induction for function

Question

I am an undergrad Computer Engineering Student that is struggling through a class in discrete mathematics. One question in particular from a recent assignment has me stumped. Assuming that $T$ is a total non decreasing function that maps from Z+ to R+, also that $k \in Z^{+}$, and $T(2^{k}) = T(2^{k-1})+5$, and that $T(1)=7$ prove by induction that

$T(2^k) = 5k + 7$

I am confused about where to begin this. I would take my base case as k=0 from the expression im asked to prove, but then what is the inductive hypothesis and where would i go from there for the inductive step? I appreciate any kind of help. Thanks

Answer 1

The case $k=0$ is ok by the hypothesis $T(1)=7$, since $ 2^0=1$. Then suppose for $k> 0$ that the relation is true. Calculate $T(2^{k+1})=T(2^k)+5= 5k+ 7 +5$ by inductive hypothesis; finally you have only to rearrange the right part writing $5k +7 +5= 5(k+1) +7$.

Answer 2

Step one: Find all elements up to k-1 By assuming T(2^k-1) = 5(k - 1) + 7 Step two: Then add the kth term (2^k) to a closed form of the above equation, 5(k - 1) + 7

If the equations are the same you have proved by induction.

Base case as described in question for completeness of answer: T(1) = 7 T(2^(0)) = 5(0) + 7 T(1) = 7