0
  1. Let $T(0) = 0$ and $T(n) = 1 + T(n/2)$ for $n > 0$. Which one of the following is a solution for $T(n)$ when $n = 2^{m}$.

a. $T(2^{m}) = m + 1$

b. $T(2^{m}) = m$

c. $T(2^{m}) = m - 1$

d. $T(2^{m}) = 2m$

e. $T(2^{m}) = 2^{m}$

  1. $f$ a recurrence relation $S(k)$ has the characteristic equation $x^{2} - 6x + 9 = (x - 3)^{2}$ then which one of the following is the correct form of the general solution of $S(k)$?

Select one:

a. $a3^{k} + b3^{k}$

b. $a(-6)^{k} + b9^{k}$

c. $(a + bk)(-3)^{k}$

d. $a3^{k}$

e. $(a + bk)3^{k}$

Could help me solve the approach to solving these substitution problems, I know the answers are a and e respectively, but I start I am not able to arrive at those answers . Thanks for any help

Alex Ravsky
  • 90,434
user2287434
  • 3
  • Are you sure $T(0)=0$ is given initial condition? – Prajwal Kansakar Jun 04 '17 at 02:30
  • yes that was given as an intial condition – user2287434 Jun 04 '17 at 02:34
  • If $T(0)=0$ and $T(n)=1+T(n/2)$ then $T(0)=1+T(0)$ so therefore $0=1$. On the other hand if rather than $T(0)=0$ the initial condition is that $T(1)=1$ then it follows that $T(2^m)=1+T(2^{m-1})=\cdots=m+T(2^{m-m})=m+1$. – John Wayland Bales Jun 04 '17 at 04:22
  • I see it specified that the second condition holds only for $n>0$ but the two conditions as stated provide no definition for $T(1)$, so as stated the correct answer is $T(2^m)=m+T(1)$. So I still contend that the first condition was supposed to be $T(1)=1$ since that is the only conditition consistent with $(a)$ being the intended answer. – John Wayland Bales Jun 04 '17 at 04:33