Find a formula for a recursion

Question

I have the following reccurence:

$$f(n)=3f\left(\frac{n}{2}\right)+4, \quad f(1)=1 \text{ and } n=2^k.$$

The task is to find a formula, that depends only on $n$ and prove it by induction. I have calculated some values of this recursion,

$$f(2)=7, f(4)=25, f(8)=79,$$

but I did't find any relation between these numbers.

Answer 1

You start from $$f(2n)=3f(n)+4$$

To remove the constant, notice that a constant solution would verify $a=3a+4\iff a=-2$.

So we will set $f(n)=g(n)-2$ to reduce the equation to $$g(2n)=3g(n)$$

Now take $n=2^k$ then $g(2^k)=3g(2^{k-1})=3^2g(2^{k-2})=\cdots=3^kg(2^0)=3^kg(1)$

Since we have $g(1)=f(1)+2=3$ then $g(2^k)=3^{k+1}$.

Finally substituting $k=\log_2(n)$ you get: $$\large{f(n)=3^{\log_2(n)+1}-2}$$

Answer 2

Solving the recurrrence

For recurrence relations on this particular form, you can use the Master Method. I will not describe what the method is, since it can be found in several books.

We can set the variables $a = 3$ and $b = 2$ and the function $f(n) = 4$. We will use a test case to test which of the 3 cases of the Master Method is the solution.

$n^{log_b(a)} = n^{log_2(3)}$

It can be seen that $f(n) \leq n^{log_2(3)}$. Therefore, we use case 1 as the solution. Case 1 states that the solution to the recurrence is $\Theta(n^{log_b(a)}) = \Theta(n^{log_2(3)})$.

Proving the result

To prove the result, induction is the most efficient proof technique for this particular problem. We will start out with the basis step for the lowest value, which is 0 for the equation

$f(n) = 3f(\frac{n}{2}) + 4 \leq \Theta(n^{log_2(3)})$.

Basis step

First of all, you haven't defined the result of $f(0)$, so I will just assume $f(0) = -2$.

Then, it can be seen that

$f(n) = 3f(\frac{0}{2}) + 4 = 3 * (-2) + 4 = -2 \leq \Theta(0^{log_2(3)})$

is true.

Inductive step

We now it must be true that

$f(n) = 3f(\frac{n}{2}) + 4 \leq \Theta(n^{log_2(3)})$.

Therefore, it also holds for any $k \geq n$. This implies the equation is true for $k + 1$:

$f(k) = 3f(\frac{k + 1}{2}) + 4 \leq \Theta((k + 1)^{log_2(3)})$.

We will insert $\Theta(k^{log_2(3)})$ into the function definition:

$f(k) = 3 * (\frac{k + 1}{2})^{log_2(3)}$

$= 3 * \frac{(k + 1)^{log_2(3)}}{2^{log_2(3)}}$

$= 3 * \frac{(k + 1)^{log_2(3)}}{3^{log_2(2)}}$

$= \frac{3 * (k + 1)^{log_2(3)}}{3}$

$= (k + 1)^{log_2(3)}$,

and our proof is complete.

Answer 3

Given is the following recursive sequence:

$f(1)=1, \ f(n)=3f\left(\frac{n}{2}\right)+4, \ n = 2^k , \ k \geq 1$

Calculating the first elements $7$ elements of this sequence:

$f(2^0)=f(1)=1$

$f(2^1)=3f(2^0)+4=3f(1)+4=7$

$f(2^2)=3f(2^1)+4=3 \cdot 7+4=25 = 7 + 2\cdot 3^2$

$f(2^3)=3f(2^2)+4=3 \cdot 25+4=79 = 7 + 2\cdot(3^2 + 3^3) $

$f(2^4)=3f(2^3)+4=3 \cdot 79+4=241 = 7 + 2\cdot(3^2 + 3^3 + 3^4)$

$f(2^5)=3f(2^4)+4=3 \cdot 241+4=727 = 7 + 2\cdot(3^2 + 3^3 + 3^4 + 3^5)$

$f(2^6)=3f(2^5)+4=3 \cdot 727+4=2185= 7 + 2\cdot(3^2 + 3^3 + 3^4 + 3^5+3^6)$

$ \hspace{1cm}\vdots \hspace{5cm} \vdots \hspace{5cm} \vdots $

We can observe a pattern and we get for $k \geq 2$ the algebraic function $f(2^k) = 7+2 \cdot \sum_{j=2}^{k}3^j$

I obtained this result by calculating the differences $$f(2^1)-f(2^0),f(2^2)-f(2^1),f(2^3)-f(2^2),f(2^4)-f(2^3),f(2^5)-f(2^4),f(2^6)-f(2^5),\cdots $$ or the differences $$7-1,25-7,79-25,241-79,727-241,2185-727,\cdots$$ or the differences $$6,18,54,162,486,1458,\cdots$$ or the differences $$2\cdot 3^1,2\cdot 3^2,2 \cdot 3^3,2 \cdot 3^4,2\cdot 3^5,2\cdot3^6,\cdots$$ between the elements of the sequence $$f(2^0), f(2^1), f(2^2), f(2^3), f(2^4), f(2^5), f(2^6), \cdots $$ or the elements of the sequence $$7,25,79,241,727,2185,\cdots$$

The algebraic function $f(2^k) = 7+2 \cdot \sum_{j=2}^{k}3^j$ can be simplified using the geometric progression as follows

$$\begin{align*} 7+2 \cdot \sum_{\color{red}{j=2}}^{k}3^j &= 7+2 \cdot \left( \left(\sum_{\color{red}{j=0}}^{k}3^{j}\right) - 3^0 - 3^1\right) \\&= 7+2 \cdot \left( \sum_{j=0}^{k}3^{j}\right) - 2 \cdot\left(3^0 + 3^1\right) \\&= 7+\frac{2(1-3^{k+1})}{1-3} - 8 \\&= 7+\frac{2(1-3^{k+1})}{-2} - 8 \\&= 7-(1-3^{k+1}) - 8 \\&=7-1+3^{k+1}-8 \\&=3^{k+1}-2 \end{align*} $$

Suddenly, this function $f(2^k) = 3^{k+1}-2$ works now for every $k \geq 0$.

To calculate $\sum_{j=2}^{k}3^j$ in the function $f(2^k) = 7+2 \cdot \sum_{j=2}^{k}3^j$ without having to refer to any formulas or to wikipedia you simply give this sum a name like $$x = \sum_{j=2}^{k}3^j = 3^2 + 3^3 + \cdots + 3^k$$ Now multiply each side of the above equation by $3$ $$3x = 3(3^2 + 3^3 + \cdots + 3^k) = 3^3+3^4+\cdots + 3^{k+1}$$ Then subtract $x$ from $3x$ $$3x-x = (3^3+3^4+\cdots + 3^{k+1})-(3^2 + 3^3 + \cdots + 3^k)= 3^{k+1} - 3^2 $$ From this last equation we have $$ 3x-x = 2x = 3^{k+1} - 3^2 $$ That's why we get $$x = \frac{1}{2}\left(3^{k+1} - 3^2\right)$$ This means that $$ \begin{align*} f(2^k) &= 7+2 \cdot \sum_{j=2}^{k}3^j \\&= 7+2 \cdot x \\&= 7+2 \cdot \frac{1}{2}\left(3^{k+1} - 3^2\right) \\&= 7+ 3^{k+1} - 9\\&= 3^{k+1} - 2\end{align*}$$

A more elegant approach with less calculation effort was given in another answer by the user zwim. This solution depends on describing the limiting behaviour of the sequence and on the fixed point of the recursion equation function (which evaluated to $-2$ in this case). Some more details are described for example in this nice paper.

Anyway, after calculating I noticed that we could have written the results also like this (because $7 =1+ 2\cdot 3^1$):

$f(2^0)=f(1)=1$

$f(2^1)=3f(2^0)+4=3f(1)+4=1+2 \cdot 3^1$

$f(2^2)=3f(2^1)+4=3 \cdot 7+4=25 = 1 + 2\cdot (3^1 + 3^2)$

$f(2^3)=3f(2^2)+4=3 \cdot 25+4=79 = 1 + 2\cdot(3^1 + 3^2 + 3^3) $

$f(2^4)=3f(2^3)+4=3 \cdot 79+4=241 = 1 + 2\cdot(3^1 + 3^2 + 3^3 + 3^4)$

$f(2^5)=3f(2^4)+4=3 \cdot 241+4=727 = 1 + 2\cdot(3^1 + 3^2 + 3^3 + 3^4 + 3^5)$

$f(2^6)=3f(2^5)+4=3 \cdot 727+4=2185= 1 + 2\cdot(3^1 + 3^2 + 3^3 + 3^4 + 3^5+3^6)$

$ \hspace{1cm}\vdots \hspace{5cm} \vdots \hspace{5cm} \vdots $

This gives the function $f(2^k) = 1 + 2 \cdot \sum_{j=1}^{k}3^j$, which evaluates to the same result $$\large{f(2^k) = 3^{k+1}-2}$$

So, this isn't a big deal.

If $n=2^k$, then $k=\log_2(n)$ and $$\large{f(n) = 3^{\log_2(n)+1}-2}$$

The next step is to prove with the help of the principle of induction that the formulas $f(n) = 3f\left(\frac{n}{2}\right)+4$ and $f(n) = 3^{\log_2(n)+1}-2$ are equal or generate the same sequence elements for each and every $n$.

For $n = 1$ it follows from the recursive sequence formula (see the very first line above) that

$$f(1) = 1$$

and it follows from the algebraic sequence formula $f(n) = 3^{\log_2(n)+1}-2$ that $$f(1) = 3^{\log_2(1)+1}-2 = 3^{0+1}-2=1$$

So, for the so called base case of the induction proof, where $n=1$, the statement

$$\text{result from recursive formula } = \text{result from explicit formula}$$

is true or it is true that the explicit/algebraic formula and the recursive formula give the same first sequence element, which equals $1$ in both cases.

Then assume that for a very special $n \geq 1$ both formulas are equivalent. Assume that for the value of $f(n)$ we have the following equation (The assumption of the induction proof):

$$3^{\log_2(n)+1}-2 = 3 f\left(\frac{n}{2}\right)+4$$

This is assumed as a true statement for a specific $n\geq 1$. We can assume it's true, since the statement is true for $n=1$. So far the assumption of the induction proof.

Then moving to the conclusion of the induction proof: Show that both sequence formulas are also equal or that the same equation holds for the exact next natural number $n+1$ after $n$. Show that the following statement (The conclusion of the induction proof)

$$ 3^{\log_2(n+1)+1}-2 = 3 f\left(\frac{n+1}{2}\right)+4$$

is true.

Using the assumption or using the equation $f(n)=3^{\log_2(n+1)}-2$, which was assumed to be true in the assumption, and using the rules $\log_a(b/c)=\log_a b -\log_a c$ and $\log_x(x)=1$, we get:

$$\begin{align*}f\left(\frac{n+1}{2}\right) &= 3^{\log_2\left(\frac{n+1}{2}\right)+1}-2 \\&=3^{\log_2\left(n+1\right)-\log_2(2)+1}-2\\&=3^{\log_2\left(n+1\right)}-2\end{align*}$$

Now we found out that $f\left(\frac{n+1}{2}\right) = 3^{\log_2\left(n+1\right)}-2$, so $$3f\left(\frac{n+1}{2}\right) = 3 \left(3^{\log_2\left(n+1\right)}-2\right) = 3^{\log_2\left(n+1\right)+1}-6$$

Finally we have now, what needed to be shown:

$$\begin{align*}3 f\left(\frac{n+1}{2}\right)+4 &= 3^{\log_2\left(n+1\right)+1}-6+4 \\&= 3^{\log_2\left(n+1\right)+1}-2\end{align*}$$

With the príncipe of induction the conclusion follows from the assumption for all natural numbers.