고조파 시리즈의 큰 세타 표기법이 theta (logn)임을 증명하고 싶습니다. 나는이를 나타 내기 위해 integral과 함께 사용합니다.고조파 시리즈의 큰 세타 표기법
내가하는 방식이를 보여 주려고 해요 : beacuse, 자사가 작동하지 이런 식으로
**ln(n)=integral [1 to n] dx/x <= sum k=1 to n of 1/k <= 1 + integral [2 to n] dx/x = 1 + ln(n)**
은 "1"내가 고조파 시리즈의 꽉 bounde 세타는 것을 증명하기 위해 캔트 (logn) .
내가 어떻게 이것을 보여줄 수 있고이 장애물을 극복 할 수 있습니까? 도와주세요.
감사합니다.
범위를 확보하는 좋은 방법 중 하나는 상위 단어 또는 하위 단어의 합계를 각 용어에 적용하는 것입니다. 예 :
1 + 1/2 + 1/3 + 1/5 + 1/6 + 1/7 + 1/8> = 1 + 1/4 + 1 + 4 + 1/8 + 1/8 + 1/8 + 1/8
그런 다음 (1/4 + 1/4) = 1/2 및 그룹 (1/8 + 1/8 + 1/8 + 1/8) = 1/2이고 계속 진행합니다. 당신은 결국 "몇 번"의 합을 얻게됩니다. 몇 번이나? 음, log_2 (n)을 여러 번 - 그 이유를 알아 내기 위해 당신에게 남겨 둘 것입니다.
비슷한 방법으로 예상치를 높일 수 있습니다. 또는 더 쉬운 방법은 통합을 사용하는 것입니다. [n, n + 1]의 범위에서 x에 대해 1/(x-1)> = 1/n입니다.
이렇게 1 + 1/2 + 1/3 + 1/4 + ... + 1/n < = 1 + 2/n 1/(x-1) dx의 정수).
나는 inegral을 사용하려고했지만 1 + ln (n)을 얻었고, 고조파 시리즈에 대해 위쪽 바운드를 증명하는 데 도움이되지 않습니다. – user11001
1 + ln (n) <= 2 * ln (n) n> = e 인 경우 – TravisJ
n 항의 고조파 계열 합을 증명하려면 big-theta n이라는 것을 명심하기 만하면된다. c1 * ln (n) <= HS (n) <= c2 * ln (n)이되도록 양의 정수 c1과 c2를 구한다. c1은 매우 작을 수 있고 (상수 인 한) c2는 매우 클 수 있습니다 (상수 일 경우). – TravisJ