Let f(n)= 5 f(n/ 2) + 3 and f(1) = 7. Find f(2k) where k is a positive integer.Also estimate f(n) if f is an increasing function.

To solve the recurrence relation given by \( f(n) = 5f(n/2) + 3 \) with the initial condition \( f(1) = 7 \), we can use the method of iteration to find a pattern and derive a general formula for \( f(n) \). Our goal is to express \( f(2k) \) for a positive integer \( k \) and also estimate \( f(n) \) under the assumption that \( f \) is an increasing function.

Step-by-Step Iteration

Let's start by substituting values into the recurrence relation to see how \( f(n) \) evolves:

• For \( n = 1 \):

  We know \( f(1) = 7 \).

• For \( n = 2 \):

  Using the recurrence, we have:

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

• For \( n = 4 \):

  Now substituting \( n = 4 \):

  \( f(4) = 5f(2) + 3 = 5 \cdot 38 + 3 = 190 + 3 = 193 \).

• For \( n = 8 \):

  Next, we calculate \( f(8) \):

  \( f(8) = 5f(4) + 3 = 5 \cdot 193 + 3 = 965 + 3 = 968 \).

Identifying a Pattern

From our calculations, we have:

• \( f(1) = 7 \)
• \( f(2) = 38 \)
• \( f(4) = 193 \)
• \( f(8) = 968 \)

Next, let's look for a general formula. Notice that each time we double \( n \), the function seems to grow significantly. We can express \( f(2^k) \) in terms of \( k \).

General Formula Derivation

To derive a formula, we can express \( f(2^k) \) recursively:

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

Now, substituting \( f(2^{k-1}) \) recursively:

• \( f(2^{k-1}) = 5f(2^{k-2}) + 3 \)
• Continuing this substitution leads to a series:

After \( k \) iterations, we can express it as:

• \( f(2^k) = 5^k f(1) + 3(5^{k-1} + 5^{k-2} + ... + 5^0) \)

The series \( 5^{k-1} + 5^{k-2} + ... + 5^0 \) is a geometric series that sums to:

\( \frac{5^k - 1}{5 - 1} = \frac{5^k - 1}{4} \).

Thus, we can rewrite \( f(2^k) \) as:

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

Combining these terms gives:

\( f(2^k) = \frac{20 \cdot 5^k + 3 \cdot 5^k - 3}{4} = \frac{23 \cdot 5^k - 3}{4} \).

Final Expression for f(2k)

Now, substituting \( n = 2k \) into our derived formula, we find:

\( f(2k) = \frac{23 \cdot 5^k - 3}{4} \).

Estimating f(n) for Increasing Function

Since \( f(n) \) is an increasing function, we can estimate \( f(n) \) for any \( n \) that is a power of 2. For general \( n \), we can use the fact that \( f(n) \) grows exponentially due to the \( 5^k \) term. Thus, we can say:

For large \( n \), \( f(n) \) behaves like \( O(5^{\log_2 n}) \), which simplifies to \( O(n^{\log_2 5}) \), indicating that \( f(n) \) grows faster than linear but slower than quadratic.

This gives us a good estimate of how \( f(n) \) behaves as \( n \) increases, confirming that it is indeed an increasing function.