What will be the closed formula for the following recursive function?

Question

What will be the closed formula for the following recursive function?

F(n) = F(n/2) +1 if n is even

F(n) = F(n-1) + 1 if n is odd

F(1) = 0

How do we generate closed formula for such recursive functions?

Thanks.

Answer 1

$\newcommand{\+}{^{\dagger}}% \newcommand{\angles}[1]{\left\langle #1 \right\rangle}% \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}% \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}% \newcommand{\dd}{{\rm d}}% \newcommand{\isdiv}{\,\left.\right\vert\,}% \newcommand{\ds}[1]{\displaystyle{#1}}% \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}% \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}% \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}% \newcommand{\ic}{{\rm i}}% \newcommand{\imp}{\Longrightarrow}% \newcommand{\ket}[1]{\left\vert #1\right\rangle}% \newcommand{\pars}[1]{\left( #1 \right)}% \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}}% \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}% \newcommand{\sech}{\,{\rm sech}}% \newcommand{\sgn}{\,{\rm sgn}}% \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}}% \newcommand{\verts}[1]{\left\vert #1 \right\vert}% \newcommand{\yy}{\Longleftrightarrow}$

$\large\tt Hint:$

$\ds{{\cal F}\pars{z} \equiv \sum_{n = 1}^{\infty}{\rm F}\pars{n}\,z^{n}\,,\qquad z \in {\mathbb Z}\,,\quad\verts{z} < 1}$.

\begin{align} {\cal F}\pars{z} &= \sum_{n = 0}^{\infty}{\rm F}\pars{2n + 1}\,z^{2n + 1} + \sum_{n = 0}^{\infty}{\rm F}\pars{2n + 2}\,z^{2n + 2} \\[3mm]&= {\rm F}\pars{1}z + \sum_{n = 1}^{\infty}\bracks{{\rm F}\pars{2n} + 1}\,z^{2n + 1} + \sum_{n = 0}^{\infty}{\rm F}\pars{2n + 2}\,z^{2n + 2} \\[3mm]&= \sum_{n = 0}^{\infty}\bracks{{\rm F}\pars{2n + 2} + 1}\,z^{2n + 3} + \sum_{n = 0}^{\infty}{\rm F}\pars{2n + 2}\,z^{2n + 2} \\[3mm]&= \pars{z + 1}\sum_{n = 0}^{\infty}{\rm F}\pars{2n + 2}\,z^{2n + 2} + {z^{3} \over 1 - z^{2}} = \pars{z + 1}\sum_{n = 0}^{\infty}\bracks{{\rm F}\pars{n + 1} + 1}\,z^{2n + 2} + {z^{3} \over 1 - z^{2}} \\[3mm]&= \pars{z + 1}\sum_{n = 1}^{\infty}{\rm F}\pars{n}\,z^{2n} + \pars{z + 1}\,{z^{2} \over 1 - z^{2}} + {z^{3} \over 1 - z^{2}} \end{align}

$$ {\cal F}\pars{z} = \pars{z + 1}{\cal F}\pars{z^{2}} + {z^{2} \over 1 - z} + {z^{3} \over 1 - z^{2}} $$