Skip to main content
added 13 characters in body; added 8 characters in body; edited body; deleted 2 characters in body
Source Link

Rewriting the recursion yields $$1 = \sum\limits_{1\leq i \leq k} \frac{i\ f(i)}{k+i-1}.$$ By assuming $f(k)=\frac{1}{k \ln 2} (1+o(1))$, --- where the little o-Notation $o(1)$ simply means that isit is smaller than every constant for large $k$, --- and inserting this, we get $$\sum\limits_{1\leq i \leq k} \frac{i\ f(i)}{k+i-1} = \frac{1}{\ln 2} \sum\limits_{1\leq i \leq k} \frac{1+o(1)}{k+i-1} = \frac{1+o(1)}{\ln 2} \left(\ln (2k-1)-\ln(k)\right) = \frac{1+o(1)}{\ln 2} \ln\left(2-\frac1k\right) \to 1 $$ for $k\to\infty$. I used $\sum_{1\leq i \leq k} = \ln k + \gamma + O(1/n)$$\sum_{1\leq i \leq k} \frac1i = \ln k + \gamma + o(1)$. Therefore the assumtion holds asymptotically, since it fulfils the recursion.

The bound $f(k)<2/k$ follows from that --- at least, there is an $K$, such that for all $k\geq K$ the inequality $f(k)<2/k$ holds.

Rewriting the recursion yields $$1 = \sum\limits_{1\leq i \leq k} \frac{i\ f(i)}{k+i-1}.$$ By assuming $f(k)=\frac{1}{k \ln 2} (1+o(1))$, where the little o-Notation simply means that is is smaller than every constant for large $k$, and inserting this, we get $$\sum\limits_{1\leq i \leq k} \frac{i\ f(i)}{k+i-1} = \frac{1}{\ln 2} \sum\limits_{1\leq i \leq k} \frac{1+o(1)}{k+i-1} = \frac{1+o(1)}{\ln 2} \left(\ln (2k-1)-\ln(k)\right) = \frac{1+o(1)}{\ln 2} \ln\left(2-\frac1k\right) \to 1 $$ for $k\to\infty$. I used $\sum_{1\leq i \leq k} = \ln k + \gamma + O(1/n)$. Therefore the assumtion holds asymptotically, since it fulfils the recursion.

The bound $f(k)<2/k$ follows from that --- at least, there is an $K$, such that for all $k\geq K$ the inequality $f(k)<2/k$ holds.

Rewriting the recursion yields $$1 = \sum\limits_{1\leq i \leq k} \frac{i\ f(i)}{k+i-1}.$$ By assuming $f(k)=\frac{1}{k \ln 2} (1+o(1))$ --- where the little o-Notation $o(1)$ simply means that it is smaller than every constant for large $k$ --- and inserting this, we get $$\sum\limits_{1\leq i \leq k} \frac{i\ f(i)}{k+i-1} = \frac{1}{\ln 2} \sum\limits_{1\leq i \leq k} \frac{1+o(1)}{k+i-1} = \frac{1+o(1)}{\ln 2} \left(\ln (2k-1)-\ln(k)\right) = \frac{1+o(1)}{\ln 2} \ln\left(2-\frac1k\right) \to 1 $$ for $k\to\infty$. I used $\sum_{1\leq i \leq k} \frac1i = \ln k + \gamma + o(1)$. Therefore the assumtion holds asymptotically, since it fulfils the recursion.

The bound $f(k)<2/k$ follows from that --- at least, there is an $K$, such that for all $k\geq K$ the inequality $f(k)<2/k$ holds.

Source Link

Rewriting the recursion yields $$1 = \sum\limits_{1\leq i \leq k} \frac{i\ f(i)}{k+i-1}.$$ By assuming $f(k)=\frac{1}{k \ln 2} (1+o(1))$, where the little o-Notation simply means that is is smaller than every constant for large $k$, and inserting this, we get $$\sum\limits_{1\leq i \leq k} \frac{i\ f(i)}{k+i-1} = \frac{1}{\ln 2} \sum\limits_{1\leq i \leq k} \frac{1+o(1)}{k+i-1} = \frac{1+o(1)}{\ln 2} \left(\ln (2k-1)-\ln(k)\right) = \frac{1+o(1)}{\ln 2} \ln\left(2-\frac1k\right) \to 1 $$ for $k\to\infty$. I used $\sum_{1\leq i \leq k} = \ln k + \gamma + O(1/n)$. Therefore the assumtion holds asymptotically, since it fulfils the recursion.

The bound $f(k)<2/k$ follows from that --- at least, there is an $K$, such that for all $k\geq K$ the inequality $f(k)<2/k$ holds.