How to solve this series $f(n) = f(n/2) + n$?

Question

Can I solve this as: $f(n) = f(n/2) + n$ let find, $$f(n/2) = f(n/2/2) + n/2\\ f(n/2) = f(n/4) + n/2$$ Now, $$\begin{split} f(n) &= f(n/4) + n/2 + n\\ f(n) &= f(n/8) + n/4 + n/2 + n \end{split}$$ hence so on. $$\vdots$$ Now, $n = 2^i$. $$\begin{split} f(2^i) &= f(2^i/2^i) + 2^i/2^{i-1} + 2^i/2^{i-2} + \cdots + 2^i\\ f(2^i) &= f(1) + 2^1 + 2^2 + \cdots + 2^i\\ f(2^i) &= 2^0 + 2^1 + 2^2 + \cdots + 2^i\\ f(2^i) &= 2^{i+1} - 1\\ f(2^i) &= 2^i\cdot 2^1 - 1\\ f(n) &= 2n - 1\\ f(2^k) &= f(2^{k-k}) + k\\ f(2^k) &= f(2^0) + k\\ \cdots &= f(1) + k\\ \cdots &= 1 + k \end{split}$$ As we know $$\begin{split} n &= 2^k\\ \log (n) &= k \log(2)\\ k &= \log (n) / \log(2)\\ k &= \log_2 (n)\\ f(n) &= \log_2(n) + 1 \end{split}$$

Answer 1

At some point you need to have the value of say $f(1)$ or something. The classical way of solving this kind of questions would be to do as you did until:

$$ f(n) = f(1) + \sum_{i=0}^{k} \frac{n}{2^i}$$

where $2^k = n$. Then you should be able to solve the problem by computing $\sum_{i=0}^{k} \frac{n}{2^i}$ using geometric series.

In the case you $n$ is not a power of $2$, you must apply the reccurence formula until step $k$ with $\frac{n}{2^k} \le 1$, and the you must know what is the value of $f$ of say, interval $[0,1]$.

Answer 2

You’ve just given a recursion. A recursion needs have a base to be well defined. The base here could be the set of all $x \in (0.5, 1]$ (then any $x>0$ can be uniquely written as $2^kx_0$ for some $k\in\mathbb Z$ and $x_0\in (0.5,1]$).

So choose for one such $x_0$ a $y_0$ and define $f(x_0) := y_0$. Then suppose $n = 2^ky_0$. This gives the recursion

$$ f_0(0) = y_0 $$ $$ f_0(k) = f_0(k-1) + 2^ky_0 $$ Thus $$ f_0(k) = y_0\left(\sum_{i=0}^k 2^k\right) = y_0(2^{k+1}-1)$$

If $n = y_02^k$ then $k = \log_2 n - \log_2{y_0}$. Also as $y_0\in(0.5,1]$ we have $\log_2y_0 \in (-1, 0]$. So $k = \lfloor \log_2 n \rfloor$, $y_0 = 2^{\{\log_2 n\}}$ (where $\{x\} := x - \lfloor x \rfloor$ is the fractional part).

Thus given any function $g:(0.5, 1]\to\mathbb R$ and the condition $f|{(0.5,1]} = g$ the solution to your recursion will be given by

$$ f(n) = g(2^{\{\log_2 n\}})(2^{\lfloor \log_2 n\rfloor + 1} - 1) $$

or alternatively using $g^*:(-1:0]\to\mathbb R$ with $g^*(x) := g(2^x)$ we get

$$ f(n) = g^*(\{\log_2 n\})(2^{\lfloor \log_2 n\rfloor + 1} - 1) $$

Answer 3

Given $$f(n) = f(n/2) + n$$ for all even integers $n\geq 2$, substitute the linear ansatz $f(n)= A n + B$ to yield $$A n + B = A/2 n + B/2 + n.$$ Comparing coefficients of $n^1=n$ and of $n^0=1$ yields the constraint equations $$A = A/2 + 1$$ and $$B=B/2$$ which are simultaneously solved only by $A=2$ and $B=0$. So

$$f(n)=2n$$ is the only affine function satisfying the recurrence relation.

Similarly, the more general ansatz $$f(n)= \sum_{k=0}^\infty A_k n^k$$ yields that all higher $A_k=0$ for $k\geq 2$.

Alternatively, one can assume there is a second solution $g(n)\neq f(n)$ for the appropriate $n$ and arrive at a contradiction. So $$f(n)=2n$$ is the only solution.