Sometimes solving exactly a recurrence can be demanding. The use of software can be useful 🙂

Something that I slept under the rag above and I want to mention it since this post by no means is supposed to be intimidating to a novice, is that in many applications (lemmas,theorems etc.) one needs the asymptotic behavior of the recurrence and this CAN be done in many cases.

Now the problem of the day for you is the following: find the asymptotic behavior of the recurrence . If you also can, find except for the main term, the second term too.