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

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

• Your definition of $T(n)$ seems to be missing some parentheses, and maybe a $T$? I have attempted to fix it, let me know if I understood correctly. – Inactive - Objecting Extremism Mar 5 at 1:08
• @Servaes please wait for a response before changing the meaning of their math. – The Great Duck Mar 5 at 1:09
• @TheGreatDuck The math was syntactically incorrect, and the rest of the question strongly suggested this was the intended meaning. And your edit wasn't a rollback, so don't call it that. – Inactive - Objecting Extremism Mar 5 at 1:10
• @Servaes Your edit is correct. Thanks! – user140161 Mar 5 at 1:13
• @Servaes Yes, it was a rollback. I removed your edit. – The Great Duck Mar 6 at 0:42

By induction $$T(N)=N$$; the base case $$N=1$$ holds by definition.
Suppose $$T(n)=n$$ for all $$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}$$.
• Beware, we need to have $\dfrac{N+1}2<N\iff N>1\iff N\ge 2$ for the induction to be not self-referencing. So $T(2)$ should also be verified as initial step. – zwim Mar 5 at 1:13
• @zwim You are right that this proof of the induction step is only valid for $N\geq2$. But $T(2)$ need not be verified because the base case $N=1$ has already been verified, so the first application of the induction step is with $N=2$. – Inactive - Objecting Extremism Mar 5 at 1:22
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$$