Question

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

Short answer

Thus, the result is:

\(f(n) = 5{n^{{{\log }_3}2}} - 4\)

Step-by-step solution

Theorem 1 definition

When\(n = {b^k}\)and\(a \ne 1\), where\(k\) is a positive integer,

\(f(n) = {C_1}{n^{{{\log }_b}a}} + {C_2},\)Where\({C_1} = f(1) + c/(a - 1)\) and\({C_2} = - c/(a - 1)\).

Apply Theorem 1

We have\(f(n) = 2f(n/3) + 4,f(1) = 1\)

Use the notation of the book, we have,\(a = 2,b = 3,c = 4\)

Use Theorem 1 of the chapter we have:

\(\begin{array}{*{20}{l}}\begin{array}{l}f(n) = {C_1}{n^{{{\log }_b}a}} + {C_2}\\f(n) = {C_1}{n^{{{\log }_3}2}} + {C_2}\end{array}&{}\\\begin{array}{c}{C_1} = f(1) + \frac{c}{{a - 1}}\\ = 1 + \frac{4}{{2 - 1}}\\ = 5\\{C_2} = \frac{{ - c}}{{a - 1}}\\ = \frac{{ - 4}}{{2 - 1}}\\ = - 4\end{array}&{}\\{}&{}\end{array}\)

Thus, the result is:

\(f(n) = 5{n^{{{\log }_3}2}} - 4\)