Multiple choice

Consider the following recurrence relation

$T(1)=1$

$T(n+1) = T(n)+\lfloor \sqrt{n+1} \rfloor$ for all $n \geq 1$

The value of $T(m^2)$ for $m \geq 1$ is

  1. $\frac{m}{6}\left(21m-39\right)+4$
  2. $\frac{m}{6}\left(4m^2-3m+5\right)$
  3. $\frac{m}{2}\left(3m^{2.5}-11m+20\right)-5$
  4. $\frac{m}{6}\left(5m^3-34m^2+137m-104\right)+\frac{5}{6}$
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

T (1) = 1 T(n+1) = T(n) + $\lfloor \sqrt(n+1) \rfloor $ for all n$\ge$1 If n = m2 - 1 T(m2) = T(m2 - 1) + $\lfloor m \rfloor $ T(2) = T(1) + $\lfloor \sqrt(2) \rfloor $ = 1 + 1= 2 T(3) = T(3) + $\lfloor \sqrt(3) \rfloor $ = 2 + 1= 3 T(4) = T(3) + 2 = 5 T(5) = 5 + 2 = 7 T(6) = 7 + 2 = 9 T(7) = 9 + 2 = 11 T(8) = 11 + 2 = 13 T(9) = 13 + 3 = 16 T(10) = 16 + 3 = 19 T(11) = 19 + 3 = 22 T(12) = 22 + 3 = 25 T(13) = 25 + 3 = 28 T(14) = 28 + 3 = 31 T(15) = 31 + 3 = 34 T(16) = 34 + 4 = 38 T(m2) = T(m2 - 1) + $\lfloor m \rfloor $ Put m = 2 T(4) = T(3) + 1 = 4 Put m = 2 T (9) = T(8) + 1 = 13 + 1 = 14 (a) $\dfrac{m}{6}$(21m - 39) + 4 Put m = 2, $\dfrac{2}{6}$(42 - 39 ) + 4 = 5 Put m = 3, $\dfrac{3}{6}$(63 - 39 ) + 4 = 16 Put m = 4, $\dfrac{4}{6}$(84 - 39) + 4 = $\dfrac{2}{4}$x 45 + 4 = 34 (b) Put m = 2, $\dfrac{m}{6}$(4m2 - 3m + 5 ) = $\dfrac{2}{6}$[ 16 - 6 + 5 = 5 Put m = 3, $\dfrac{3}{6}$[4 x 9 - 3 x 3 + 5 ] = $\dfrac{1}{2}$[32] = 16 Put m = 4, $\dfrac{4}{6}$[64 - 12 + 5] = $\dfrac{2}{3}$[57] = 38 Hence, choice (b) satisfies the solution of T(m2)

Keep practicing — related questions