Solution

The correct answer is 5K(31/4) - 3/4

To solve the recurrence relation f(n) = 5 f(n/2) + 3 with f(1) = 7 , we will use the method of iteration to find f(2^K) .

First, let's iterate the recurrence:

1. \(f(2^K) = 5 f(2^{K-1}) + 3\)
2. \(f(2^{K-1}) = 5 f(2^{K-2}) + 3\)
3. Continue this process until \(f(2^1) = 5 f(2^0) + 3\)

We know \(f(2^0) = f(1) = 7 .\)

By substituting back, we can express f(2^K) in terms of f(1) :

\(f(2^K) = 5 f(2^{K-1}) + 3\)

\(f(2^{K-1}) = 5 f(2^{K-2}) + 3\)

\(\vdots\)

\(f(2^1) = 5 f(2^0) + 3 = 5 \cdot 7 + 3 = 35 + 3 = 38\)

Now we see a pattern:
\(f(2^2) = 5 f(2^1) + 3 = 5 \cdot 38 + 3 = 190 + 3 = 193\)

Continuing this process, we can generalize the solution. Each time we apply the recurrence, we multiply the previous term by 5 and add 3.

We can express this as:
\(f(2^K) = 5^K f(1) + 3 \sum_{i=0}^{K-1} 5^i\)

The sum \(\sum_{i=0}^{K-1} 5^i\) is a geometric series, which can be summed as:

\(\sum_{i=0}^{K-1} 5^i = \frac{5^K - 1}{5 - 1} = \frac{5^K - 1}{4}\)

So the expression becomes:

\(f(2^K) = 5^K \cdot 7 + 3 \cdot \frac{5^K - 1}{4}\)


\(f(2^K) = 5^K \cdot 7 + \frac{3(5^K - 1)}{4} \)

\(f(2^K) = 5^K \cdot 7 + \frac{3 \cdot 5^K - 3}{4}\)


\(f(2^K) = \frac{4 \cdot 7 \cdot 5^K + 3 \cdot 5^K - 3}{4} \)

\(f(2^K) = \frac{28 \cdot 5^K + 3 \cdot 5^K - 3}{4}\)


\(f(2^K) = \frac{31 \cdot 5^K - 3}{4}\)

Thus, the correct answer is: \(1) 5^K \left(\frac{31}{4}\right) - \frac{3}{4}\)