Is $\log^* (n+1)^{n+2} \in O(\log^* n)$?

87 Views Asked by At

I would like to know if $\log^* (n+1)^{n+2} \in O(\log^* n)$, where $\log^*$ is the iterated logarithm.

I tried doing:

$ \log^* (n+1)^{n+2} =\\ \log^{*}(\log(n+1)^{n+2})-1 =\\ \log^{*}((n+2) \cdot \log(n+1))-1 =\\ \log^{*}(\log((n+2)\cdot \log (n+1)))-2 =\\ \log^{*}(\log(n+2) + \log\log (n+1))-2 =\\ \log^{*}(O(\log n))-2 =\\ O(\log^{*}n)$

...but:

  1. I'm not sure the operations are correct (probably, they are not).
  2. I don't know how to prove O(\log^{-1}n) = O(\log^ n).