I came u with the following equation:
$T(2) = 1$
$T(n) = \lfloor \frac {n} {2}\rfloor + T(\lceil \frac{n}{2} \rceil) | n ∈ \mathbb N$
But I can't find a way to solve it. Is there one?
I need to proof that the solution is right, so I can't just look at the numerical sequence of the equation.
On
You can solve this as follows. First calculate the first few values \begin{align} T(3) = 1 + T(2) = 2 \\ T(4) = 2 + T(2) = 3 \\ T(5) = 2 + T(3) = 4 \\ T(6) = 3 + T(3) = 5 \end{align} Ok, it might be that T(n) = n - 1. Let's try to prove this by induction. Firstly, we have $T(2) = 1$ so this is obviously true for $n = 2$. Now assume it is true for $n = 2, 3 , \dots k$ and we would now like to prove it for $n= k+1$. \begin{equation} T(k+1) = \left\lfloor \frac{k+1}{2} \right\rfloor + T \left( \left\lceil \frac{k+1}{2}\right\rceil\right). \end{equation} Now, we must consider two different cases. Either $k+1$ is even or odd. If $k$ is even the above equation becomes \begin{equation} T(k+1) = \frac{k+1}{2} + T\left( \frac{k+1}{2} \right) = \frac{k+1}{2} + \left( \frac{k+1}{2} - 1 \right) = (k+1) - 1 . \end{equation} Above I used that we have assumed that $T(n) = n-1$ for $n\leq k$ in the second step. Now assume that $k+1$ is odd. We then get \begin{equation} T(k+1) = \frac{k+1}{2} - 0.5 + T\left(\frac{k+1}{2} + 0.5 \right) = \frac{k+1}{2} - 0.5 + \left(\frac{k+1}{2} + 0.5 -1 \right) = (k+1)-1. \end{equation} Hence, by the induction principle, this is true for all $n$.
On
Notice the identity $n = \left\lfloor \frac{n}{2} \right\rfloor + \left\lceil \frac{n}{2}\right\rceil$. Subtract $n$ from both sides of original identity, we get
$$T(n) - n = T\left(\left\lceil \frac{n}{2}\right\rceil\right) - \left\lceil \frac{n}{2}\right\rceil$$
Now start from $m > 2$, if one repeat apply the transform $m \mapsto \left\lceil \frac{m}{2}\right\rceil$, one always end at $m = 2$.
From this, we can conclude for any $n \ge 2$,
$$T(n) - n = T(2) - 2 = 1 - 2 = -1 \quad\implies\quad T(n) = n - 1$$
First, calculate the first few numbers in the sequence:
$T(3)=1+T(2)=2$
$T(4)=2+T(2)=3$
$T(5)=2+T(3)=4$
$T(6)=3+T(3)=5$
$T(7)=3+T(4)=6$
So now we suspect that $T(n)=n-1$, and we shall prove it by induction. Proof for the base case: $T(2)=2-1=1$, as defined. Assume this property is correct for any number less than m and splits cases where m is even and m is odd. The even case: $T(2n) = \lfloor \frac {2n} {2}\rfloor + T(\lceil \frac{2n}{2} \rceil) = \lfloor n\rfloor + T(\lceil n \rceil) = n + n - 1 = 2n - 1$.
And the odd case: $T(2n+1) = \lfloor \frac {2n+1} {2}\rfloor + T(\lceil \frac{2n+1}{2} \rceil) = \lfloor n+\frac {1} {2}\rfloor + T(\lceil n+\frac{1}{2} \rceil) = n + T(n+1) = n + n = 2n$. Thus, by the principle of strong induction, $T(n)=n-1$ is true for all $n\ge2$.