Find recurrence relation equation to the following algorithm

Question

It has been estimated that a specific social network site has the following number of users per month.

F(n)= F(n-1)*120% + 100*n  where F(0)=0    

this means that every month 100 new users are added because of advertisement and 20% more users are added per month due to users inviting people the the social network. Also on the first month there are no users.

Anyways if we plug in numbers to this recursion we will get:

F(0)=0
F(1)=F(0)*1.2 + 100*1=100
F(2)=F(1)*1.2 + 100*2=320
F(3)=F(2)*1.2 + 100*3=684
F(4)=F(3)*1.2 + 100*4=1220.8
F(5)=F(4)*1.2 + 100*5=1964.96
....

Anyways I have answer the first part of that question. Now I am stuck in solving that recursive relation. I need to find an equation that will solve the recurrence relation. In other words a function that if I where to pass the number 2 then it will output 320 for example without having to call itself.

The answer is actually:

I don't understand how to get to that solution. I got that answer from HERE. I will like to understand how to solve it not just get the solution.

Answer 1

Mathematical View

instead of 1.2 I'll use a and instead of 100 I'll use b (a>1,b!=0):

F(n) = aF(n-1) + bn ==>
F(n) = a (aF(n-2) + bn) + bn 
     = a^2 F(n-2) + ab(n-1)+bn 
     = a^3F(n-2) + a^2 * b * (n-2)+a*b*(n-1)+b*n=...
     = a^n F(0) + a^(n-1) * b * (n-(n-1)) + .... + bn
     = 0 + a^(n-1)* nb + a^(n-2)* (n-1)b + ... + a^0 *1*b -
           [a^(n-1)* (n-1)b + a^(n-2) * (n-2)b + ... + 0)

if we write:

A = a^(n-1)* nb + a^(n-2)* (n-1)b + ... + a^0 *1*b
B = a^(n-1)* (n-1)b + a^(n-2) * (n-2)b + ... 

You need to find A-B.

then

A = b (a^n + a^n-1 + a^n-2 + ....)'
B = b/a * (a^(n-1)+....)' - a

and if we let C = a^n + a^n-1 + a^n-2 + .... we know C = (a^(n+1) - a)/(a - 1) and simply you can calculate C' and finally you can calculate A and B and their difference A - B.

Algorithmic and real working view

But if I want to talk in context of algorithms, I'm care about O and Θ and Ω , ... not about exact running time.

So when I see your algorithm I say It's Θ(aⁿ) without any calculation, because if you replace bn with 1, it doesn't affect your Θ notation because your function grows exponentially so removing some constant or polynomial functions (without converting them to zero) doesn't change exponential running time, and It just removes some polynomial function from final result. So in this cases I never try solid maths. I'll use solid math in writing academic papers or exams not in real life.