I have $T:$ $\mathbb{N} \rightarrow \mathbb{N}$
Such that $T(1)=1$,
$T(n)=T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil)$ for all $n\ge2$.
My work:
If $n$ is even then $\lceil n/2 \rceil = \lfloor n/2 \rfloor=n/2$.
If $n$ is odd, then we have $\lceil n/2 \rceil -1 = \lfloor n/2 \rfloor=(n-1)/2$.
Using the above results, we have
\begin{eqnarray*}
T(n)&=&2T(n/2)&\quad\text{ if n is even, }\\
T(n)&=& T((n-1)/2)+ T((n+1)/2)&\quad\text{ if n is odd.}
\end{eqnarray*}
I conjecture that $T(n)=n$ for all n.
I proved the base case for $n=2$ and then assumed that the formula is true for $n=k$. Now I will try to prove that it is also true for $n=k+1$.
I know that $k+1$ can either be odd or even, so I have to consider both possibilities, but i'm not sure how to proceed here. I appreciate any help
Best Answer
By induction $T(N)=N$; the base case $N=1$ holds by definition.
Suppose $T(n)=n$ for all $n<N$. Then if $N$ is even $$T(N)=T(\lfloor\tfrac{N}{2}\rfloor)+T(\lceil\tfrac{N}{2}\rceil)=T(\tfrac{N}{2})+T(\tfrac{N}{2})=\tfrac{N}{2}+\tfrac{N}{2}=N,$$ and similarly, if $N$ is odd, $$T(N)=T(\lfloor\tfrac{N}{2}\rfloor)+T(\lceil\tfrac{N}{2}\rceil)=T(\tfrac{N-1}{2})+T(\tfrac{N+1}{2})=\tfrac{N-1}{2}+\tfrac{N+1}{2}=N.$$ By induction $T(N)=N$ for all $N\in\Bbb{N}$.