# Prove some identities! (Round two)

Show 40 post(s) from this thread on one page
Page 7 of 7 First ... 34567
• Feb 6th 2011, 07:00 AM
PaulRS
Quote:

Originally Posted by Bruno J.

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

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

$\displaystyle (*)$ Here $\displaystyle d(k)$ is the number of positive integers dividing $\displaystyle k$.
$\displaystyle (**)$ For the case $\displaystyle n=2$ to work, we write $\displaystyle 0^0 = 1$
• Feb 6th 2011, 08:23 AM
Unbeatable0
Quote:

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

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

Let

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

Then

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

Differentiating more, it's easily seen that

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

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

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

$\displaystyle \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

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

up to $\displaystyle n-2$ times differentiation.

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

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

also does.
• Feb 6th 2011, 10:56 AM
chiph588@
Quote:

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

$\displaystyle \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 \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 \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)$

$\displaystyle \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 \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 \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)$

$\displaystyle \displayatyle = \frac12\log^2x + 2\gamma\log x + O(1)$.
• Feb 7th 2011, 03:50 AM
PaulRS
My solutions:

1.
First proof: Consider the set of functions from a set $\displaystyle A\to B$.
If we fix a subset $\displaystyle S\subseteq B$ we have that the number of functions from $\displaystyle A\to B$ such that $\displaystyle f(A)\subseteq B - S$ is $\displaystyle \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 $\displaystyle f(A)\supseteq B$ which is of course absurd since in this case $\displaystyle |f(A)|\leq |A| = n-2<|B| = n$

Remark: If $\displaystyle |A|=|B|=n$ we get $\displaystyle n! = \displaystyle\sum_{k=0}^n{\binom{n}{k}\cdot (n-k)^n\cdot (-1)^k}$, setting $\displaystyle 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 $\displaystyle n$ vertices such that a given set -you choose it- of $\displaystyle k$ labels correspond to leaves is $\displaystyle (n-k)^{n-2}$, so in fact what $\displaystyle \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 \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 $\displaystyle H_n = 1 + \tfrac{1}{2}+...+\tfrac{1}{n}$ , estimating this the rest follows.
Show 40 post(s) from this thread on one page
Page 7 of 7 First ... 34567