91Ó°ÊÓ

Solve the recurrence relation $$a_{n}=\sqrt{\frac{a_{n-2}}{a_{n-1}}}$$ with initial conditions \(a_{0}=8, a_{1}=1 /(2 \sqrt{2})\) by taking the logarithm of both sides and making the substitution \(b_{n}=\lg a_{n}\)

Write an algorithm whose worst-case time is \(O(n \lg n)\) that returns the number of inversions in a permutation of \(\\{1, \ldots, n\\}\). The algorithm's input is a permutation of \(\\{1, \ldots, n\\}\) and \(n\).

Solve the recurrence relation for the initial conditions given. \(a_{n}=-2 n a_{n-1}+3 n(n-1) a_{n-2} ; \quad a_{0}=1, \quad a_{1}=2\)

Solve the recurrence relation for the initial conditions given. \(c_{n}=2+\sum_{i=1}^{n-1} c_{i}, \quad n \geq 2 ; \quad c_{1}=1\)

Solve the recurrence relation for the initial conditions given. \(A(n, m)=1+A(n-1, m-1)+A(n-1, m), n-1 \geq m \geq 1,\) \(n \geq 2 ; A(n, 0)=A(n, n)=1, n \geq 0\)

Exercises 40-46 refer to Ackermann's function A \((m, n)\). Compute \(A(2,2)\) and \(A(2,3)\)

Exercises 40-46 refer to Ackermann's function A \((m, n)\). Use induction to show that $$ A(1, n)=n+2 \quad n=0,1, \ldots $$

Solve the recurrence relation for the initial conditions given. Show that $$f_{n+1} \geq\left(\frac{1+\sqrt{5}}{2}\right)^{n-1} \quad n \geq 1$$ where \(f\) denotes the Fibonacci sequence.

Exercises 40-46 refer to Ackermann's function A \((m, n)\). Use induction to show that $$ A(2, n)=3+2 n \quad n=0,1 \ldots $$

Exercises 40-46 refer to Ackermann's function A \((m, n)\). Guess a formula for \(A(3, n)\) and prove it by using induction.