Processing math: 70%
Google
 
Web unafbapune.blogspot.com

Wednesday, December 25, 2013

 

Ex 3.4 - 1kNHk

Prove that
  1kNHk=(N+1)(HN+11)
This proof showcases the power of OGF, ordinary generating function. Starting with the Talyer series expansion at around zero:
  OGF1=11z=N0zN
In other words, the ordinary generating function (OGF) of the sequence (1,1,,1), which are the coefficients of N0zN, is 11z.

Differentiating both sides of OGF1:
  1(1z)2=N0NzN1=N1NzN11(1z)2=N0(N+1)zNre-index
Integrating both sides of OGF1:
  ln(1z)=ln11z=N0zN+1N+1ln11z=N11NzNre-index
which means ln(11z) is the OGF for the harmonic sequence (1,12,,1N). Recall, in general, if A(z)=k0akzk is the OGF of (a0,a1,,ak,), then 11zA(z) is the OGF of (a0,a0+a1,a0+a1+a2,). So
  11zln11z=N1(1kN1N)zN=N1HNzN1(1z)2ln11z=N1(1kNHk)zN applying 11z again![zN]1(1z)2ln11z=1kNHkextract coefficient of zN
But recall from above
  1(1z)2ln11z=(N0(N+1)zN)(k11kzk)=N0k1(N+1)1kzN+k=Nkk1(Nk+1)1kzNre-index=N1(1kN(N+1k)1k)zN=N1(1kN(1k(N+1)1))zN=N1(HN(N+1)N)zN[zN]1(1z)2ln11z=HN(N+1)Nextract coefficient of zN
Now
  \begin{aligned} H_{N+1} &= H_N + \frac{1}{N+1} \\ H_N &= H_{N+1} - \frac{1}{N+1} \\ \sum_{1 \le k \le N} H_k &= (H_{N+1} - \frac{1}{N+1}) (N + 1) - N \\ &= (N + 1) H_{N+1} - 1 - N = (N + 1) H_{N+1} - (N+1) \\ \sum_{1 \le k \le N} H_k &= (N+1)(H_{N+1} - 1) \\ \end{aligned}
\Box

Source: Analysis of Algorithm


Comments: Post a Comment

<< Home

This page is powered by Blogger. Isn't yours?