In the context of Computer Science, I am trying to calculate the maximum depth difference between leaf nodes in any existing AVL-Trees of height $h$. I don't think any knowledge of AVL trees is needed, since the following terms are the stand-alone mathematical relations resulting from them.
After some reflections, the recursive term resulting of this is the following ($D(h)$ being the maximum depth difference for any possible AVL tree of height $h$):
$D(h=2)=0, D(h=3)=1$
$D(h) = \max (D(h-1), D(h-2)+1) \quad\forall h\geq4$
This is then simplified to:
$D(h) = D(h-2)+1 \quad\forall h\geq4$
Question 1: How can one assume this simplification? I believe somewhere I read something about monotone growth in it, but since there's only a recursive relation towards two terms before, there's no apparent connection between $D(h-1)$ and $D(h-2)$.
We now use telescoping to arrive at the following:
$D(h) = D(h-2)+1 = ... = D(h-2k) + k$
Question 2: How do I understand what is the condition of k, to continue telescoping until I arrive at a solution for $D(h)$?
Question 3: My intuition tells me there's going to be an even/odd distinction. How would one approach these kind of recursions for the general case of above?
$D(h) = D(h-p) + 1 \qquad \forall h\geq p$
having all the base cases: $D(0),D(1),...,D(p-1)$
Question 1 may be by induction: for $h\ge4$, let $P(h)$ be the statement $$D(h-2) \le D(h-1) \le D(h-2)+1$$
For $h=4$, check that
$$D(2) \le D(3) \le D(2)+1$$
Assume $P(k)$ is true for some $k\ge 4$:
$$D(k-2) \le D(k-1) \le D(k-2)+1$$
Then for $h=k+1$ (which compares $D(k-1)$ and $D(k)$),
$$\begin{align*} D(k) &= \max\{D(k-1), D(k-2)+1\}\\ &\ge D(k-1) \tag 1\\ D(k) &= D(k-2)+1\\ &\le D(k-1) + 1 \tag2 \end{align*}$$
From inequalities $(1)$ and $(2)$,
$$D(k-1) \le D(k) \le D(k-1)+1$$
So by mathematical induction, $\forall h\ge 4$, $P(h)$ is true and particularly $D(h-1) \le D(h-2)+1$. So
$$D(h) = D(h-2) + 1 \quad \forall h\ge 4$$
Question 2 and 3 are usually by iterating enough times and observing the pattern.
$$\begin{align*} D(h) &= D(h-2) + 1\\ &= (D(h-4) + 1) + 1 &&= D(h-4) + 2\\ &= (D(h-6) + 1) + 2 &&= D(h-6) + 3\\ &= (D(h-8) + 1) + 3 &&= D(h-\underbrace{8}_{2\cdot 4}) + 4\\ &= \vdots\\ &= D(h-2k) + k\\ \end{align*}$$
Then pick $k$ such that the argument $h-2k$ is $2$ or $3$, depending on the parity of $h$,
$$\begin{align*} h-2k &= \begin{cases} 2, &h\text{ is even}\\ 3, &h\text{ is odd}\\ \end{cases}\\ k &= \frac{h-\begin{cases} 2, &h\text{ is even}\\ 3, &h\text{ is odd}\\ \end{cases}}2\\ D(h-2k) &= \begin{cases} 0, &h\text{ is even}\\ 1, &h\text{ is odd}\\ \end{cases}\\ D(h) &= D(h-2k) + k\\ &= \frac{h + 2\cdot \left(\begin{cases} 0, &h\text{ is even}\\ 1, &h\text{ is odd}\\ \end{cases}\right) - \left(\begin{cases} 2, &h\text{ is even}\\ 3, &h\text{ is odd}\\ \end{cases}\right)} 2\\ &= \frac{h - 1 - \begin{cases} 1, &h\text{ is even}\\ 0, &h\text{ is odd}\\ \end{cases}} 2\\ &= \frac{h - 1 - ((h-1)\bmod 2)}{2}\\ &= \left\lfloor\frac {h-1}2 \right\rfloor \end{align*}$$