Asymptotically optimal $k$-step nilpotency of quadratic algebras and the Fibonacci numbers

It follows from the Golod--Shafarevich theorem that if R is an associative algebra given by n generators and $d<\frac{n^2}{4}\cos^{-2}(\frac{\pi}{k+1})$ quadratic relations, then R is not k-step nilpotent. We show that the above estimate is asymptotically optimal, and establish number of related results. For example, we show that for any k this estimate is attained for ifinitely many n.
Comment: to appear in Combinatorica