A recurrence relation
From: fei (fei.liu_at_msa.hinet.net)
Date: 02/28/05
- Next message: Lester Zick: "Re: Existence of mathematical entities (Re: Successor Axiom: on what grounds TF?)"
- Previous message: examachine_at_gmail.com: "Re: Existence of mathematical entities (Re: Successor Axiom: on what grounds TF?)"
- Next in thread: r.e.s.: "Re: A recurrence relation"
- Reply: r.e.s.: "Re: A recurrence relation"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: 28 Feb 2005 13:13:13 -0800
Hello
I have a question about the following recurrence:
T(1)= 1
T(n)= nT(n-1)+ 1
Let C(n,k) = ``n choos k".
It's known T(n) = C(n,0)*0! + C(n,1)*1! + C(n,2)*2! + ... + C(n,n-1)*(n-1)!.
So T(n) < 1 + n + n^2 + n^3 + ... + n^(n-1) = O(n^(n-1)).
Dose T(n) have a closed form or tighter bound?
Thank You!
Fei
- Next message: Lester Zick: "Re: Existence of mathematical entities (Re: Successor Axiom: on what grounds TF?)"
- Previous message: examachine_at_gmail.com: "Re: Existence of mathematical entities (Re: Successor Axiom: on what grounds TF?)"
- Next in thread: r.e.s.: "Re: A recurrence relation"
- Reply: r.e.s.: "Re: A recurrence relation"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
