$a_1,a_2,a_3,...$ is integer sequence defined recursively by
$1)a_1=0$
$2)$ for $n\gt 1$, $a_n=1+a_{\lceil{n\over 2}\rceil}$
Find an explicit formula for $a_n$ and prove it is correct.
Formula is $a_n=\lceil{\log_2(n)}\rceil$. Base case is $n=2:a_2=1+a_1=1=\log_2(2)$.$\space\space$Assume true for $1\lt k\le n$.$\space\space$Then $a_{n+1}=1+a_{\lceil{{n+1}\over 2}\rceil}\space$ where $\lceil{{n+1}\over 2}\rceil$ must fall within the range of $k$ for $n\gt 1$.$\space\space$So $a_{n+1}=1+a_{\lceil{{n+1}\over 2}\rceil}=1+\lceil{\log_2({{n+1}\over 2})}\rceil=1+\lceil{\log_2(n+1)}\rceil-\lceil{1}\rceil=\lceil{\log_2(n+1)}\rceil$ and that completes the proof by Mathematical Induction Strong/Alternative form.
In the same way it can be shown the $a_n=\log_2(n)$. This proof is incorrect. The correct proof separates the cases of $n+1$ into $2^m$ and $2^m+r$. $r,m\in Z^+$, $0\lt r \lt 2^m$. After the inductive assumption is made. Why? Why is the above proof incorrect? thanks.
The base of the logarithm should be $2$.
Because the following part is not correct :
It should be the following : $$a_{n+1}=1+a_{\lceil\frac{n+1}{2}\rceil}=1+\left\lceil\log\left\lceil\frac{n+1}{2}\right\rceil\right\rceil\tag1$$
Now whether $n+1$ is of the form $2^m$ or not matters.
If $n+1=2^m$, then $$(1)=1+\left\lceil\log(2^{m-1})\right\rceil=1+m-1=m=\lceil\log(n+1)\rceil$$
If $n+1=2^m+r$ where $0\lt r\lt 2^m$, then $$(1)=1+\left\lceil\log\left\lceil\frac{2^m+r}{2}\right\rceil\right\rceil=1+m=\lceil\log(n+1)\rceil$$