Can you pls check if I got the correct answer with correct steps done? Dont chnage the format of how I did the problem just fix any errors in the same format if any.$(5$ points$)$ Solve the following recurrence using the Back Substitution method, and check

your results with the Master Theorem Show ALL your work including at least three sub$-$

stitutions before you move to $k$ steps, and computed summations. No eredit will be given if

students don't show all their work in detail

$T(n)=16T(\frac{n}{2})+n^3+n+1$

$T(n)=16T(\frac{n}{2})+n^3+n+1$

$T(n)={16}^{2}T(\frac{n}{2^2})+\frac{n}{2^2}+n^3+n+1$

$T(n)={16}^{3}T(\frac{n}{2^3})+\frac{n^3}{2^4}+\frac{n}{2^2}+n^3+n+1$

$T(n)={16}^{4}T(\frac{n}{2^4})+\frac{n^3}{2^6}+\frac{n}{2^2}+n^3+n+1$

After $K$ steps...

$T(n)={16}^{k}T(\frac{n}{2^k})+n(\frac{16}{2}+\frac{{16}^2}{2^2}+\frac{{16}^3}{2^3}+$cdots$+\frac{{16}^{k-1}}{2^{k-1}})$

$T(n)={16}^{lo{g}_{2}n}T(1)+n({\displaystyle \underset{i=0}{\overset{k-1}{}}}(\frac{{16}^3}{2}{)}^i)$

$T(n)=n^{lo{g}_{2}16}T(1)+n({\displaystyle \underset{i=0}{\overset{k=1}{}}}(8{)}^i)=n(\frac{8^{k-1}}{7})$

$T(n)={\displaystyle \underset{i=D}{\overset{k=1}{}}}{16}^i=\frac{{16}^k-1}{15}$

$8+8=16$

$8+7=15$

$T(n)=n^{lo{g}_{2}16}T(1)+n^3(2^{lo{g}_{2}n}-1)+n(\frac{8^{lo{g}_{2}n}-1}{7})+\frac{{16}^{lo{g}_{2}n}-1}{15}$