Finding and proving a closed form formula for a recursive formula with floor and ceiling functions

Question

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

Answer 1

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}$.

Answer 2

Definitely $T(n)=n$ is a solution $$ T\left( n \right) = n = T\left( {\left\lfloor {n/2} \right\rfloor } \right) + \left\lceil {n/2} \right\rceil $$ because $$ n = \left\lfloor {n/2} \right\rfloor + \left\lceil {n/2} \right\rceil \quad \left| {\;\forall n \in \mathbb Z} \right. $$ and $$ T\left( 1 \right) = 1 $$