Question

Find \(f(n)\) when\(n = {4^k}\), where \(f\) satisfies the recurrence relation\(f(n) = 5f(n/4) + 6n\), with\(f(1) = 1\).

Short answer

The required expressions are:

\(\begin{array}{l}f(n) = {5^{{{\log }_4}n + 2}} - 6 \cdot {4^{{{\log }_4}n + 1}}\\f\left( {{4^k}} \right) = {5^{k + 2}} - 6 \cdot {4^{k + 1}}\end{array}\)

Step-by-step solution

Given expression

\(\begin{array}{c}f(n) = 5f(n/4) + 6n\\f(1) = 1\end{array}\)

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 find\(f(n)\)

Let \({a_k} = f\left( {{4^k}} \right)\) and use\(n = {4^k}\).

\(\begin{array}{l}{a_k} = 5{a_{k - 1}} + 6 \cdot {4^k}{a_0}\\{a_k} = f\left( {{4^0}} \right)\\{a_k} = f(1)\\{a_k} = 1\end{array}\)

\({a_k} = 5{a_{k - 1}}\)

Let \({a_k} = r\) and \({a_{k - 1}} = 1\)

\(r = 5\)(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.

\(a_k^{(h)} = \alpha \cdot {5^k}\)

\(F(k) = 6 \cdot {4^k}\)

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

\(a_k^{(p)} = {p_0} \cdot {4^k}\)

The particular solution needs to satisfy the recurrence relation:

\(\begin{array}{l}{a_n} = 5{a_{k - 1}} + 6 \cdot {4^k}{p_0} \cdot {4^k}\\{a_n} = 5{p_0} \cdot {4^{k - 1}} + 6 \cdot {4^k}\end{array}\)

\(\begin{array}{l} - {p_0} = 24\\{p_0} = - 24\end{array}\)

Thus, the particular solution then becomes:

\(\begin{array}{l}a_k^{(p)} = {p_0} \cdot {4^k}\\a_k^{(p)} = - 24 \cdot {4^k}\end{array}\)

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

\(\begin{array}{l}{a_k} = a_k^{(h)} + a_k^{(p)}\\{a_k} = \alpha \cdot {5^k} - 24 \cdot {4^k}\end{array}\)

Check the solution that satisfies the initial condition

The solution needs to satisfy the initial condition \({a_0} = 1\) :

\(\begin{array}{l}1 = {a_0}\\{a_0} = \alpha \cdot {5^0} - 24 \cdot {4^0}1\\{a_0} = \alpha - 2425\\{a_0} = \alpha \end{array}\)

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

\(\begin{array}{l}{a_k} = \alpha \cdot {5^k} - 24 \cdot {4^k}\\{a_k} = 25 \cdot {5^k} - 24 \cdot {4^k}\\{a_k} = {5^{k + 2}} - 6 \cdot {4^{k + 1}}\end{array}\)

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

\(\begin{array}{l}f(n) = f\left( {{4^k}} \right)\\f(n) = {5^{k + 2}} - 6 \cdot {4^{k + 1}}\\f(n) = {5^{{{\log }_4}n + 2}} - 6 \cdot {4^{{{\log }_4}n + 1}}\end{array}\)