找出以下算法的递推关系方程式

Question

据估计，某个特定的社交网络网站每月有以下数量的用户。

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

这意味着每个月有100个新用户因为广告加入，每个月由于用户邀请社交网络中的人，增加了20%的用户。另外，在第一个月没有用户。

无论如何，如果我们将数字代入到这个递归公式中，我们会得到：

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
....

无论如何，我已经回答了那个问题的第一部分。现在我陷入了解决那个递归关系的困境中。我需要找到一个方程来解决这个递归关系。换句话说，如果我传递数字2，则输出320的函数，而无需调用自身。

答案实际上是：

我不明白如何得出这个解决方案。我从此处得到了这个答案。我想理解如何解决它，而不仅仅是得到答案。

- Tono Nam

Answer 1

数学视角

我将使用a代替1.2，使用b代替100（其中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)

如果我们写：

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 + ... 

你需要找到A-B。

然后。

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

如果我们让C = a^n + a^n-1 + a^n-2 + ....，我们知道C = (a^(n+1) - a)/(a - 1)，然后你可以计算出C'，最终你可以计算出A和B以及它们的差异A - B。

算法和实际工作视角

但是，如果我想在算法的上下文中谈论，我关心O、Θ和 Ω等，而不是确切的运行时间。

因此，当我看到你的算法时，我会说它是Θ(aⁿ)，无需进行任何计算，因为如果你将bn替换为1，它不会影响你的Θ符号，因为你的函数呈指数增长，所以删除一些常量或多项式函数（不将它们转化为零）不会改变指数级运行时间，它只是从最终结果中删除了一些多项式函数。因此，在这种情况下，我从不尝试坚实的数学。我会在写学术论文或考试时使用实心数学，而不是在现实生活中使用它。

- Saeed Amiri

Answer 2

F(n)=A*F(n-1)+B*n

这里看起来像是一个带有线性加法的指数。

我们的想法是找到C和D，使得以下等式成立：

F(n)+C*n+D=A*(F(n-1)+C*(n-1)+D)

然后我们可以引入另一个函数：G(n)=F(n)+C*n+D

G(n)=A*G(n-1)

G(n)=E*A^n（E可以从起始条件中找到）

F(n)=A^n-C*n-D

现在让我们实际找到C和D：

B*n=A*C*(n-1)+A*D-C*n-D=(A*C-C)*n+A*D-D-A*C

B=C*(A-1) - 这将给我们C

0=A*D-D-A*C - 这将给我们D（前提是已知C）

- maxim1000

Answer 3

f(n)=af(n-1)+bn =a[af(n-2)+b(n-1)+b(n-1)]=a^2f(n-2)+(a+1)b(n-1) -ab

一般来说， f(n) =a^n * x + n*y+z

现在， f(1)=a*x+y+z=1 f(2)=(a^2)* x+2y+z= f(3)=...

我们可以解这个线性系统，得到x、y、z。

- user1105089

Answer 4

我希望早些时候我就提出了这个解决方案。这是我想出的答案，我猜测因为我得到了一个（非递归）的等式，这可能是正确的解决方案。

- Tono Nam