How to solve this series $f(n) = f(n/2) + n$? 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}$$
 A: 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]$.
A: 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) $$
A: 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.
