Question

Solve the recurrence relation $\mathit{T}\mathbf{\left(}\mathit{n}\mathbf{\right)}\mathbf{=}\mathit{n}{\mathit{T}}^{\mathbf{2}}\mathbf{(}\mathit{n}\mathbf{/}\mathbf{2}\mathbf{)}$with the initial condition$\mathit{T}\mathbf{\left(}\mathbf{1}\mathbf{\right)}\mathbf{=}\mathbf{6}$when$\mathit{n}\mathbf{=}{\mathbf{2}}^{\mathbf{k}}$for some integer. [Hint: Let$\mathit{n}\mathbf{=}{\mathbf{2}}^{\mathbf{k}}$and then make the substitution${\mathit{a}}_{\mathbf{k}}\mathbf{=}\mathit{l}\mathit{o}\mathit{g}\mathit{T}\mathbf{\left(}{\mathbf{2}}^{\mathbf{k}}\mathbf{\right)}$to obtain a linear non-homogeneous recurrence relation.]

Short answer

Thus, the result is;

$T\left(n\right)=\frac{6^n{4}^{n-1}}{n}$

Step-by-step solution

Linear Homogeneous Recurrence Relations with Constant Coefficients definition

Suppose that $\left\{a_n\right\}$satisfies the linear non-homogeneous recurrence relation

${\mathit{a}}_{\mathbf{n}}\mathbf{=}{\mathit{c}}_{\mathbf{1}}{\mathit{a}}_{\mathbf{n}\mathbf{-}\mathbf{1}}\mathbf{+}{\mathit{c}}_{\mathbf{2}}{\mathit{a}}_{\mathbf{n}\mathbf{-}\mathbf{2}}\mathbf{+}\mathbf{\cdots }\mathbf{+}{\mathit{c}}_{\mathbf{k}}{\mathit{a}}_{\mathbf{n}\mathbf{-}\mathbf{k}}\mathbf{+}\mathit{F}\mathbf{\left(}\mathit{n}\mathbf{\right)}\mathbf{,}$Where${\mathit{c}}_{\mathbf{1}}\mathbf{,}{\mathit{c}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{c}}_{\mathbf{k}}$are real numbers, and

$\mathit{F}\mathbf{\left(}\mathit{n}\mathbf{\right)}\mathbf{=}\mathbf{(}{\mathbf{b}}_{\mathbf{f}}{\mathbf{n}}^{\mathbf{t}}\mathbf{+}{\mathbf{b}}_{\mathbf{f}\mathbf{-}\mathbf{1}}{\mathbf{n}}^{\mathbf{t}\mathbf{-}\mathbf{1}}\mathbf{+}\mathbf{\cdots }\mathbf{+}{\mathbf{b}}_{\mathbf{1}}\mathbf{n}\mathbf{+}{\mathbf{b}}_{\mathbf{0}}\mathbf{)}{\mathit{s}}^{\mathbf{n}}\mathbf{,}$Where${\mathit{b}}_{\mathbf{0}}\mathbf{,}{\mathit{b}}_{\mathbf{1}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{b}}_{\mathbf{t}}$and$\mathit{s}$are real numbers.

When$\mathit{s}$is not a root of the characteristic equation of the associated linear homogeneous recurrence relation, there is a particular solution of the form$\mathbf{(}{\mathbf{p}}_{\mathbf{t}}{\mathbf{n}}^{\mathbf{t}}\mathbf{+}{\mathbf{p}}_{\mathbf{t}\mathbf{-}\mathbf{1}}{\mathbf{n}}^{\mathbf{t}\mathbf{-}\mathbf{1}}\mathbf{+}\mathbf{\cdots }\mathbf{+}{\mathbf{p}}_{\mathbf{1}\mathbf{n}}\mathbf{+}{\mathbf{p}}_{\mathbf{0}}\mathbf{)}{\mathit{s}}^{\mathbf{n}}$

Whena root of this characteristic equation and its multiplicity is is$\mathit{m}$, there is a particular solution of the form:${\mathit{n}}^{\mathbf{m}}\mathbf{(}{\mathbf{p}}_{\mathbf{t}}{\mathbf{n}}^{\mathbf{t}}\mathbf{+}{\mathbf{p}}_{\mathbf{t}\mathbf{-}\mathbf{1}}{\mathbf{n}}^{\mathbf{t}\mathbf{-}\mathbf{1}}\mathbf{+}\mathbf{\cdots }\mathbf{+}{\mathbf{p}}_{\mathbf{1}}\mathbf{n}\mathbf{+}{\mathbf{p}}_{\mathbf{0}}\mathbf{)}{\mathit{s}}^{\mathbf{n}}\mathbf{.}$

Use Recurrence Relations

Equation is:$T\left(n\right)=n{T}^2(n/2)T\left(1\right)=6$

Let $n=2^k$then:$T\left(2^k\right)=2^k{T}^2\left(2^k/2\right)=2^k{T}^2\left(2^{k-1}\right)$

Let $a_k={\log }_T\left(2^k\right)$then:

$$\begin{gathered} a_k={\log }_{2}T\left(2^k\right) \\ {a}_k={\log }_2\left(2^k{T}^2\left(2^{k-1}\right)\right) \\ {a}_k={\log }_2\left(2^k\right)+{\log }_2\left(T^2\left(2^{k-1}\right)\right) \\ {a}_k=k+{\log }_2\left({\left(T\left(2^{k-1}\right)\right)}^2\right) \\ {a}_k=k+2{\log }_2\left(T\left(2^{k-1}\right)\right) \\ {a}_k=k+2a_{k-1} \end{gathered}$$

Thus we have then found the recurrence relation $a_n=2a_{n-1}+n$with $a_0={\log }_{2}T\left(2^0\right)={\log }_{2}T\left(1\right)={\log }_{2}6$.

Use Recurrence Relations again

Let$a_n=r$ and $a_{n-1}=2$(other functions of $n$are considered to be 0)

The solution of the recurrence relation is then of the form; $a_n={\alpha }_1{r}_1^n+{\alpha }_{2}n{r}_1^n+\dots +{\alpha }_k{n}^{k-1}{r}_1^n$with $r_1$a root with the multiplicity $k$of the characteristic equation.

$a_n^{\left(h\right)}=\alpha ·2^n$

Thus the solution of the homogeneous recurrence relation is$a_n^{\left(h\right)}=\alpha ·2^n$

If $F\left(n\right)=\left(b_t{n}^t+b_{t-1}{n}^{t-1}+\dots +b_{1}n+b_0\right)s^n$and $s$is not a root of the characteristic equation, then $\left(p_t{n}^t+p_{t-1}{n}^{t-1}+\dots +p_{1}n+p_0\right)s^n$is the particular solution.

If $F\left(n\right)=\left(b_t{n}^t+b_{t-1}{n}^{t-1}+\dots +b_{1}n+b_0\right)s^n$and $s$is a root of the characteristic equation with multiplicity $m_{\text{, then}}{n}^m\left(p_t{n}^t+p_{t-1}{n}^{t-1}+\dots +p_{1}n+p_0\right)s^n$is the particular solution.

1 is not a root of the characteristic equation:

$a_n^{\left(p\right)}=\left(p_{1}n+p_0\right)·1^n=p_{1}n+p_0$

Check to satisfy the Recurrence Relation

The particular solution needs to satisfy the recurrence relation:

$$\begin{gathered} a_n=2a_{n-1}+n{p}_{1}n+p_0 \\ {a}_n=2\left(p_1(n-1)+p_0\right)+n{p}_{1}n+p_0 \\ {a}_n=2p_{1}n-2p_1+2p_0+n0=p_{1}n-2p_1+p_0+n0 \\ {a}_n=\left(p_1+1\right)n+\left(-2p_1+p_0\right) \end{gathered}$$

All coefficients then need to be zero $p_1+1=0-2p_1+p_0=0$

Solve each equation $p_1=-1p_0=2p_1=2(-1)=-2$.

The particular solution then becomes:$a_n^{\left(p\right)}=p_{1}n+p_0=-1n-2=-n-2$

The solution of the non-homogeneous linear recurrence relation is the sum of the homogeneous $a_n^{\left(h\right)}$and particular solutions $a_n^{\left(p\right)}$which is:

$a_n=a_n^{\left(h\right)}+a_n^{\left(p\right)}=\alpha ·2^n-n-2$

Evaluate and simplify

Evaluate$a_n=\alpha ·2^n-n-2$ at $n=0$:

role="math" localid="1668581907140" $$\begin{gathered} {\log }_{2}6=a_0=2^0\alpha -0-2 \\ {\log }_{2}6=\alpha -2 \end{gathered}$$

Combine like terms:${\log }_{2}6+2=\alpha$

The solution of the non-homogeneous linear recurrence relation then becomes:

$$\begin{gathered} a_n=\alpha ·2^n-n-2 \\ {a}_n=\left({\log }_{2}6+2\right)·2^n-n-2 \\ {a}_n={\log }_{2}6·2^n+2^{n+1}-n-2 \end{gathered}$$

Since $a_k={\log }_{2}T\left(2^k\right)$then:${\log }_{2}T\left(2^k\right)={\log }_{2}6·2^n+2^{n+1}-n-2$

Take the exponential with the baseof each side:

$$\begin{gathered} T\left(2^k\right)=2^{{\log }_{2}T\left(2^k\right)} \\ T\left(2^k\right)=2^{{\log }_{2}6·2^k+2^{k+1}-k-2} \\ T\left(2^k\right)=6^{2^k}{2}^{2^{k+1}}{2}^{-k}{2}^{-2} \\ T\left(2^k\right)=\frac{6^{2^k}{\left(2^2\right)}^{2^k}}{2^k{2}^2} \\ T\left(2^k\right)=\frac{6^{2^k}{4}^{2^k}}{4·2^k} \end{gathered}$$

Let$n=2^k$, then:

.$$\begin{gathered} T\left(n\right)=T\left(2^k\right) \\ T\left(n\right)=\frac{6^{2^k}{4}^{2^k}}{4·2^k} \\ T\left(n\right)=\frac{6^n{4}^n}{4·n} \end{gathered}$$

$T\left(n\right)=\frac{6^n{4}^{n-1}}{n}$