1
$\begingroup$

I find that the above nonlinear recurrence could be written as the following $n^{2}T(n)=(n-1)^{2}T(n-1)-(n-1)T(n-1)+3$. Then, I let $\alpha(n) = nT(n-1)$. However, I am stuck here. I don't know how to solve it. Hope that someone could give me some hint about it.

$\endgroup$
2
$\begingroup$

I think you made a type, however defining $\alpha(n) := n T(n)$ leads to the following expression: $$ n \alpha(n) = (n-2)\alpha(n-1) + 3. $$ We know that $\alpha(1) = 1$, then from this we get $\alpha(2) = 3/2$ and we notice that it is true for all $n \ge 2$. To prove this we use induction.

Assume it is true for $n - 1$, i.e. $\alpha(n - 1) = 3/2$ then $$ n \alpha(n) = (n - 2) \cdot 3/2 + 3 = n \cdot 3/2 \implies \alpha(n) = 3/2, $$ concluding the proof by induction. Hence, $\alpha(n) = 3/2$ for all $n \ge 2$.

Finally, $T(n) = \frac{3}{2n} ~ \forall n \ge 2.$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.