Prove some identities! (Round two)

Printable View

Show 40 post(s) from this thread on one page

February 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 $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$
February 6th 2011, 08:23 AM
Unbeatable0

Quote:

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.
February 6th 2011, 10:56 AM
chiph588@

Quote:

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)$ .
February 7th 2011, 03:50 AM
PaulRS

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.

Show 40 post(s) from this thread on one page