Need discreete math help!

[shikhan]

Hey guys, i'm a little baffeled by a few questions, if you could give me some tips on them:

1) [Solved!!] -> still working on 2 tho. I've got part b and a foot hold on a but... stupid big oh makes no sense

Let H(n) = sum(1/k,k,1,n)
Prove using induction that sum(H(k),k,1,n) = (n+1)H(n) - n

I started working this out but started to fiddle with both sides and that screwed up the proof the first time. Afterwords, I just get stuck. I know induction is prove base case [in this, base case is when n = 1] , then assume f(n) is true and prove f(n+1), but i can't get anywhere on this one... grr



2) Define f(n) ~< g(n) if f(n) is in O(g(n)). Define lg(n) as log base 2 of n. Define log(n) as log base 10 of n

a) prove that n lg(n) ~< n ^(10/9) but n^(10/9) is not ~< n lg(n)
b) Prove that log(n) ~< lg(n)

I kinda understand big O. I know that its defined as: if g(x) is the big O of f(x), then f(x) <= c * g(x) for some constant c, with x>k for some k

But i have no clue where to go from here... bah

 

[CSoup]

Are you CS? Sorry, been too many years, so I'm very rusty on this stuff and my brain is very tired right now. I'll look at it if I have some free time.

2a) not sure if you have the ~< in the right direction in this one, but something like the following might help.
for n > 0
if you divide by n on both sides you get lg(n) ~< n^(1/9). lg(n) = k, where 2^k = n => k = n^1/2.

You end up having root functions on both sides, but the left side is always larger for n > 1.


2b) is pretty easy I think. You know that lg(n) and log(n) are different by only a constant from the equivalence formula log base k of n = log(n)/log(k).

These are nice ones, normally you have to do induction to prove these O, theta, sigma things.

 

[HappyFace]

English please?

 

[yodayoda]

ok, here is what i got for question 1:

Step 1: Prove the base case (in this question, the n=1 case)
(replace n everywhere with 1)

sum(H(k), k, 1, 1) = (1+1)H(1) - 1
(reduce k from 1 to 1 to k=1)
H(1) = (1+1)H(1) - 1
(now calculate H(1) = sum (1/k, k, 1, 1) = 1/1 = 1
1 = (2)(1) - 1
(reduce and clean up)
1 = 1
Step 1 complete--this is a true statement

Step 2: Assume true for case n

Step 3: Prove true for the n+1 case
(replace n everywhere with n+1)

sum(H(k), k, 1, n+1) = (n+2) H(n+1) - (n+1)
(factor the left term, remove the n+1 case)
sum(H(k), k, 1, n) + H(n+1) = (n+2) H(n+1) - (n+1)
(subtract an H(n+1) from both sides)
sum(H(k), k, 1, n) = (n+1) H(n+1) - (n+1)
(reduce the H(n+1) to a H(n) and the (n+1)th term of its sum)
sum(H(k), k, 1, n) = (n+1) (H(n) + (1/(n+1))) - (n+1)
(n+1 and 1/n+1 get reduced to 1)
sum(H(k), k, 1, n) = (n+1) H(n) + 1 - (n+1)
(the +1 and the -1 term cancel each other out)
sum(H(k), k, 1, n) = (n+1) H(n) - n
(look familiar? it should, it is the nth case that you assumed true)

QED

 

[yodayoda]

ok, i formatted it so you can read it. i would work on the others but i have to go to bed. GL!

 

[shikhan]

YodaYoda!

Thanks alot!!

I saw my mistake finally... I didn't change the statement into double sums, just kept it a sum of a function... Slipped my mind. Thanks alot!