Prove some identities! (Round two)

**PaulRS** · February 6th 2011, 07:00 AM

Originally Posted by Bruno J.

Here's an easy problem I made up : show that, for any positive integer $n$ , we have

$\displaystyle \sum_{k=2}^\infty\lfloor \log_k n\rfloor = \sum_{k=1}^\infty \lfloor n^{1/k}-1\rfloor$

Simply put -since the sums are finite: $\displaystyle\sum_{k=1}^{\infty}{\lfloor \log_k n\rfloor} = \sum_{k=2}^{\infty}{\left(\sum_{k^r \leq n ; r\geq 1} 1 \right) } = \sum_{r\geq 1}\left(\sum_{k^r\leq n; k\geq 2}1\right)$

And we are done since $\displaystyle\sum_{k^r\leq n; k\geq 2}1 = \lfloor n^{1/r}-1\rfloor$

Now a couple of problems:

1. Show that: $\displaystyle\sum_{k=1}^n{\frac{d(k)}{k}} = \tfrac{1}{2}\cdot \log^2(n)+ O\left(\log(n)\right)$ $(*)$
2. Show that: $\displaystyle\sum_{k=0}^{n}{\binom{n}{k}\cdot (n-k)^{n-2}\cdot (-1)^k} = 0$ for all $n\in \{2,3,4,...\}$ $(**)$

$(*)$ Here $d(k)$ is the number of positive integers dividing $k$ .
$(**)$ For the case $n=2$ to work, we write $0^0 = 1$

**Unbeatable0** · February 6th 2011, 08:23 AM

Originally Posted by PaulRS

2. Show that: $\displaystyle\sum_{k=0}^{n}{\binom{n}{k}\cdot (n-k)^{n-2}\cdot (-1)^k} = 0$ for all $n\in \{2,3,4,...\}$

I'll assume $n\ge 3$ . For $n=2$ it can be checked directly.

Let

$\displaystyle{ f(x)=\sum_{k=0}^n \binom{n}{k}x^k = (1+x)^n }$

Then

$\displaystyle{ xf'(x)=\sum_{k=0}^n \binom{n}{k}kx^k }$

Differentiating more, it's easily seen that

$ \displaystyle x(x(xf')'\cdots)' = \sum_{k=0}^n\binom{n}{k}P_m(k)x^k}$

Where on the left side we have $m$ differentiations and on the right side $P_m$ are polynomials of degree $m$ .

As such, $\{P_0,P_1,P_2,\cdots,P_{n-2}\}$ form a basis to the vector space of polynomials of degree at most $n-2$ . Therefore,

$\displaystyle{ \sum_{k=0}^n \binom{n}{k}(n-k)^{n-2}x^k=\sum_{k=0}^n \binom{n}{k}k^{n-2}x^k }$

is a linear combination of

$ (1)\;\;\;f,\; xf',\; x(xf')'\;\cdots\;, x(x(xf')'\cdots)' $

up to $n-2$ times differentiation.

But since the zero of $f$ at $-1$ is of order $n$ , we have that all the functions in (1) evaluated at $-1$ vanish, and thus their linear combination evaluated at that point,

$\displaystyle\sum_{k=0}^n \binom{n}{k}(n-k)^{n-2}(-1)^k$

also does.

**chiph588@** · February 6th 2011, 10:56 AM

Originally Posted by PaulRS

1. Show that: $\displaystyle\sum_{k=1}^n{\frac{d(k)}{k}} = \tfrac{1}{2}\cdot \log^2(n)+ O\left(\log(n)\right)$

$\displaystyle \sum_{n\leq x} d(n) = \sum_{n\leq x} \left\lfloor\frac xn\right\rfloor = \sum_{n\leq x} \frac xn -\sum_{n\leq x}\left\{\frac xn\right\}$

$\displaystyle = x\left(\log x +\gamma x +O\left(\tfrac1x\right)\right) + O(x) = x\log x + O(x)$ .

Now use Abel's summation to get

$\displaystyle \sum_{n\leq x} \frac{d(n)}n = \frac{x\log x + O(x)}x + \int_1^x \frac{\log t}t dt + O\left(\int_1^x \frac1t dt\right)$

$\displayatyle = \frac12\log^2x + O\left(\log x\right)$ .

-------

Now I'll do you one better.

It can be shown via the Dirichlet hyperbola method that $\displaystyle \sum_{n\leq x} d(n) = x\log x + (2\gamma-1)x + O\left(\sqrt{x}\right)$ .

Now use Abel's summation to get

$\displaystyle \sum_{n\leq x} \frac{d(n)}n = \frac{x\log x + (2\gamma-1)x + O\left(\sqrt{x}\right)}x + \int_1^x \frac{\log t}t dt + \int_1^x \frac{2\gamma-1}t dt + O\left(\int_1^x t^{-3/2} dt\right)$

$\displayatyle = \frac12\log^2x + 2\gamma\log x + O(1)$ .

**PaulRS** · February 7th 2011, 03:50 AM

My solutions:

1.
First proof: Consider the set of functions from a set $A\to B$ .
If we fix a subset $S\subseteq B$ we have that the number of functions from $A\to B$ such that $f(A)\subseteq B - S$ is $\left( |B| - |S|\right)^{|A|}$ so in fact what we are counting (in the original equation) by inclusion-exclusion is the number of functions such that $f(A)\supseteq B$ which is of course absurd since in this case $|f(A)|\leq |A| = n-2<|B| = n$

Remark: If $|A|=|B|=n$ we get $n! = \displaystyle\sum_{k=0}^n{\binom{n}{k}\cdot (n-k)^n\cdot (-1)^k}$ , setting $n = p-1$ and using Fermat's Little Theorem + The Binomial Theorem we get a proof of Wilson's Theorem.

Second Proof: The number of labeled trees with $n$ vertices such that a given set -you choose it- of $k$ labels correspond to leaves is $(n-k)^{n-2}$ , so in fact what $\displaystyle\sum_{k=0}^n{\binom{n}{k}\cdot (n-k)^{n-2}\cdot (-1)^k}$ is counting is the number of trees with no leaves, of course, if there are vertices this number will be 0.

2. We write : $\displaystyle\sum_{k=1}^n{\frac{d(k)}{k}}= \sum_{k=1}^n{\tfrac{1}{k}\cdot \sum_{d|k}{1}} = \sum_{d=1}^n{\sum_{d|k}{\tfrac{1}{k}}} = \sum_{d=1}^n{\tfrac{1}{d}\cdot H_{\left\lfloor \tfrac{n}{d} \right\rfloor}}$ where $H_n = 1 + \tfrac{1}{2}+...+\tfrac{1}{n}$ , estimating this the rest follows.

Thread: Prove some identities! (Round two)

LinkBack

Thread Tools

Display

Similar Math Help Forum Discussions

Can't prove these identities?

prove the following identities.

Prove Identities

Prove these identities.

help Prove identities

Search Tags