Question

Find$f\left(n\right)$when$n=2^k$, where$f$satisfies the recurrence relation

$f\left(n\right)=8f(n/2)+n^2$ with$f\left(1\right)=1$.

Short answer

The required expressions are:

$f\left(n\right)=3·8^{{\log }_{4}n}-2·{16}^{{\log }_{4}n}$

$f\left(4^k\right)=3·8^k-2·{16}^k$

Step-by-step solution

Given expression

$$\begin{gathered} f\left(n\right)=8f(n/4)+n^2 \\ f\left(1\right)=1 \end{gathered}$$

Define the Recursive formula

A recursive formula is a formula that defines any term of a sequence in terms of its preceding terms.

Use the Recursive formula to findf(n)

Let$a_k=f\left(4^k\right)$and use$n=4^k$

localid="1668608368221" $$\begin{gathered} a_k=8a_{k-1}+4^{2k} \\ {a}_k=8a_{k-1}+{16}^k\left(4^0\right) \\ {a}_o=f\left(1\right) \\ {a}_o=1 \end{gathered}$$

Let$a_k=r$and$a_{k-1}=1$

$r=8$(Root Characteristic equation)

The solution of the recurrence relation is of the form$a_n={\alpha }_1{r}_1^n+{\alpha }_2{r}_2^n$when$r_1$and$r_2$the distinct roots of the characteristic equation.

$$\begin{gathered} a_k^{\left(h\right)}=\alpha ·8^k \\ F\left(k\right)={16}^k \end{gathered}$$

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 is not 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.

$a_k^{\left(p\right)}=p_0·{16}^k$

The particular solution needs to satisfy the recurrence relation:

$$\begin{gathered} a_n=8a_{k-1}+{16}^k \\ {p}_0.a_n=8p_0·{16}^{k-1}+{16}^k \\ 8p_0=16 \\ {p}_0=2 \end{gathered}$$

Thus, the particular solution then becomes:

$$\begin{gathered} a_k^{\left(p\right)}=p_0·{16}^k \\ {a}_k^{\left(p\right)}=2·{16}^k \end{gathered}$$

The solution of the non-homogeneous recurrence relation is the sum of the solution of the homogeneous recurrence relation and the particular solution.

$a_k=\alpha ·8^k-2·{16}^k$

Check the solution that satisfies the initial condition 

The solution needs to satisfy the initial condition$a_0=1$:

$3=\alpha$

Then use$a_k=f\left(4^k\right),n=4^k$and$k={\log }_{4}n$:

$f\left(n\right)=3.8^{{\log }_{4}n}-2·{16}^{{\log }_{4}n}$