如何获得欧米茄(n)

我有公式 a(n) = n * a(n-1) +1 ； a(0) = 0

如果没有主定理，我怎样才能从中得到 Omega、Theta 或 O 表示法，或者有人有一个很好的网站来理解解释

马斯特定理甚至不适用，所以不能使用它并不是太大的限制。

此处有效的方法是猜测上限和下限，然后如果猜测正确，则通过归纳法证明这些猜测。

a(0) = 0
a(1) = 1
a(2) = 3
a(3) = 10
a(4) = 41

对下限的合理猜测是 a(n) >= n!对于n>1。 n=1 时也是如此。假设 n=k-1 成立。

a(k) = ka(k-1)+1 
     >= k (k-1)! + 1 
     >= k!. 

因此，如果 n=k-1 成立，则 n=k 成立，因此 a(n) >= n！对于所有正整数 n，且 a(n) = Omega(n!)。

上限的合理猜测是 a(n) =1，n=k-1 成立。然后

a(k) = k(a(k-1))+1 
    <= k(2(k-1)!-1)+1 
     = 2(k!) +1-k 
    <= 2(k-1)!-1. 

因此，对于任何 n>=1，a(n)