Discrete Mathematics: Philosophy Forums

Discrete Mathematics
fUNCTIONS
Sequences and summation
the growth of function

Discrete Mathematics

Christim
Aspirant

Usergroup: Members
Joined: Feb 28, 2009

Total Topics: 17
Total Posts: 20

Posted 10/29/09 - 08:30 AM: Subject: Discrete Mathematics	#1
Show that 1^k + 2^k + 3^k + ... + (n-1)^k + n^k is ORDER n^(k+1). (where k is a positive integer)

TheSandman
Initiate

Usergroup: Members
Joined: Nov 13, 2009
Location: A computer

Total Topics: 0
Total Posts: 5

Posted 11/13/09 - 06:25 PM:	#2
I'll be honest here, I have no idea what you are talking about, but I'm extremely interested in discrete math and theory, so if you could offer some explanation, that would be highly appreciated.
"I know zoos are no longer in people’s good graces. Religion faces the same problem. Certain illusions about freedom plague them both." - Yann Martel

MathematicalPhysics Wizard
Quantum-Gravity Mechanic

Usergroup: Members
Joined: May 02, 2003

Total Topics: 105
Total Posts: 739

Posted 11/15/09 - 09:49 AM:	#3
He refers that 1^k+...+n^k=O(n^(k+1)) where big O means that the quotient: f(n)=O(g(n)) \|f(n)/g(n)\| is smaller than a positive constant. Obviously you should prove this by induction: suppose 1^k+....+n^k=O(n^(k+1)) multiply this by n to get: n+n2^k+...+n^(k+1)=O(n^(k+2)), Now f(n)=n+n2^k+...+n^(k+1)>=1+2*2^k+...+n^(k+1)=g(n) so g(n)=O(f(n))=O(n^(k+2)), because f(n)/n^(k+2)<=C, and g(n)/n^(k+2)<=f(n)/n^(k+2)<=C.
"What kind of a bomb is this? The exploding kind." Peter Sellers

Sorry, you don't have permission to post. Log in, or register if you haven't yet.