Number of all AVL trees of height K containing minimal number of nodes How do I count all AVL trees, which contain exactly the minimum number of nodes? I think that there should be some recurrent formula with Fibonacci numbers and binary logarithm.
We can count minimum number of nodes of AVL tree with height K using such formula: $amount = F(k-1) + F(k-2) + 1$, where F(n) is a Fibonacci number for n. 
 A: If we let $M(n)$ represent the number of nodes in an AVL tree of height $n$ and with minimal amount of nodes, we would get the reccurence $$M(n)=M(n-1)+M(n-2)+1$$ denote $M^{'}(n):=M(n)+1$  and we got that $$M^{'}(n)=M^{'}(n-1)+M^{'}(n-2)$$ and $$M^{'}(1)=2=F(3),M^{'}(2)=3=F(4)$$ so $M^{'}(n)=F(n+2)$ and $M(n)=F(n+2)-1$.    
Now, let $A(n)$ denote the number of AVL trees of height $n$ with minimal amount of nodes. 
The root must have $2$ children, one with height $n-1$ and the other with height $n-2$, we have $2$ options to order them (left child is higher/right child is higher). We have $A(n-1)$ options for the subtree with hight $n-1$ (it must be with minimal nodes, and $A$ is the function that gives the number of such trees). Similarly, for the smaller trees, we have $A(n-2)$ options.
We got that the overall number of options to construct a AVL tree of height $n$ with minimal number of nodes is given by the reccurence $$A(n)=2A(n-1)A(n-2),A(1)=1,A(2)=1$$
We can now use a very similar trick to the one we used to solve $M(n)$ - define $$A^{'}(n):=\log_2(A(n))+1$$ and we got that $$A^{'}(n)=A^{'}(n-1)+A^{'}(n-2),A^{'}(1)=1,A^{'}(2)=1$$ so $A^{'}=F$ (fibonacci sequence) and so $$F(n)=\log_2(A(n))+1\rightarrow A(n)=2^{F(n)-1}$$
$$\square$$
