Solve by induction.The recurrence
$\displaystyle S(n) = 1$, for $\displaystyle n=1$
$\displaystyle S(n) = [S(\frac{n}{2})]+[S(\frac{n}{2})]+1$, for $\displaystyle n \geq 2$
Hello, Apprentice123!
I believe you have misplaced the brackets . . .
If I'm right, we have a fascinating "exponential" sequence . . .Solve by induction the recurrence:
$\displaystyle S(1) = 1$
$\displaystyle S(n) \:=\:S\bigg(\!\!\left[\tfrac{n}{2}\right]\!\!\bigg) + S\bigg(\!\!\left[\tfrac{n}{2}\right]\!\!\bigg) +1$ . for $\displaystyle n \geq 2$
. . $\displaystyle \begin{array}{ccc} \text{Group} & & \text{Value} \\ \hline S(1) &=& 1 \\ S(2),S(3) &=& 3 \\ S(4),S(5),S(6),S(7) &=& 7 \\ S(8),S(9),\;\hdots\; S(15) &=& 15 \\ S(16),S(17),\hdots S(31) &=& 31 \\ \vdots & & \vdots \end{array}$
Each group doubles in length.
The $\displaystyle n^{th}$ group has the value: .$\displaystyle 2^n-1$
Good luck with the inductive proof . . .