I have been given an assignment in which to determine if
$$ lg*(lg(n)) = lg*n - 1 $$
where $n \geq 2$ and lg* denotes the iterative logarithm.
I'm fairly certain that this is true but I haven't worked with the iterative logarithm previously so I would like to affirm this.
My understanding of $log*n$ is that the iterative logarithm calculates how many times you must apply $log_2n$ until you reach or are below 1.
If this is true, then $lg*(lg(n))$ would reduce the number of times you need to apply the iterative logarithm by one.
This would have the same effect as subtracting one from the final result of the iterative logarithm. therefore:
$$ lg*(lg(n)) = lg*n - 1 $$
I'm back into the swing of things in school and an extra set of eyes would be of great assistance. Thanks.
The iterative function is defined by:
$lg(n)=0$ if $n\le1,$
$lg(n)=1+lg(log(n))$ if $n>1$.
Therefore for $n\ge2$ by definition and rearranging the equation, it's true.