Prove the following identity for every $ n\in N$: $ \sum_{j+h=n,j\geq h}\frac{(-1)^h2^{j-h}\binom{j}{h}}{j}=\frac{2}{n}$
Problem
Source: Romania TST 1991
Tags: induction, LaTeX, logarithms, combinatorics unsolved, combinatorics
02.03.2010 17:16
(Sorry, I don't know tex yet) Let a(n)= (j+h=n,j>=h) summation ( ((-1)^h).( 2^(j-h)).C(j,h) ) The problem is equivalent to proving a(n) - a(n-2) =2. By using C(n,h)= C(n-1,h)+ C (n-1,h-1), we have a(n) = 2.a(n-1)-a(n-2). a(1)=2 and a(2)=3. So by induction, a(n)=n+1. So a(n)-a(n-2)= (n+1)-(n-1) =2.
16.04.2010 17:58
Hasan, see LaTeX and http://www.artofproblemsolving.com/Forum/viewtopic.php?t=123690 for information about writing in LaTeX. I have to admit, however, that I fail to see a relationship between what the question asks and what you've written -- what has happened to the factor of $ \frac {1}{j}$ in the summation? We can rewrite our sum as $ a_{n} : = \sum_{0 \leq h \leq \frac {n}{2}} \frac {( - 1)^h 2^{n - 2h} \binom{n - h}{h}}{n - h}$. Then \begin{align*}A(x) & : = \sum_{n \geq 1} a_n x^n \\ & = \sum_{n \geq 1} x^n \sum_{0 \leq h \leq \frac {n}{2}} \frac {( - 1)^h 2^{n - 2h} \binom{n - h}{h}}{n - h} \\ & = \sum_{h \geq 0} \sum_{\substack{n \geq 2h \\ n > 0}} x^n \frac {( - 1)^h 2^{n - 2h} \binom{n - h}{h}}{n - h} \\ & = \sum_{n \geq 1} \frac {2^n \cdot x^n}{n} + \sum_{h \geq 1} \sum_{n \geq 2h} x^n \frac {( - 1)^h 2^{n - 2h} \binom{n - h}{h}}{n - h}. \end{align*} Now observe that for $ h > 0$ we have $ \frac {1}{n - h} \binom{n - h}{h} = \frac {1}{h} \binom{n - h - 1}{h - 1}$, so we may compute \begin{align*} A(x) & = - \log(1 - 2x) + \sum_{h > 0} \frac { ( - 1)^h\cdot 2^{ - 2h}}{h} \sum_{n \geq 2h} (2x)^n \binom{n - h - 1}{h - 1} \\ & = - \log(1 - 2x) + \sum_{h > 0} \frac { ( - 1)^h\cdot 2^{ - 2h}}{h} \cdot \frac {(2x)^{2h}}{(1 - 2x)^h} \\ & = - \log(1 - 2x) - \log\left(1 + \frac {x^2}{1 - 2x}\right) \\ & = - 2\log(1 - x) \\ & = \sum_{n \geq 1} \frac {2x^n}{n}, \end{align*}as needed.
17.04.2010 13:27
I've learned latex since that post, now I can write it completely: Let $ a(n)=\sum_{j+h=n,j\geq h}(-1)^{h}2^{j-h}\binom{j}{h}.$ $ \sum_{j+h=n,j\geq h}\frac{(-1)^{h}2^{j-h}\binom{j}{h}}{j}=\frac{2}{n}\iff \sum_{j+h=n,j\geq h}n\frac{(-1)^{h}2^{j-h}\binom{j}{h}}{j}=2\iff\sum_{j+h=n,j\geq h}\frac{j}{j}(-1)^{h}2^{j-h}\binom{j}{h}+\sum_{j+h=n,j\geq h}\frac{h}{j}(-1)^{h}2^{j-h}\binom{j}{h}=2\iff a(n)+\sum_{j+h=n,j\geq h}(-1)^{h}2^{j-h}\binom{j-1}{h-1}=2.$ Let $ r=\sum_{j+h=n,j\geq h}(-1)^{h}2^{j-h}\binom{j-1}{h-1}.$ $ r=(-1)^{0}2^{n}\binom{n-1}{-1}+(-1)^{1}2^{n-2}\binom{n-2}{0}+(-1)^{2}2^{n-4}\binom{n-3}{1}+\dots$ $ a(n-2)=(-1)^{0}2^{n-2}\binom{n-2}{0}+(-1)^{1}2^{n-4}\binom{n-3}{1}+\dots$ So $ r=-a(n-2)$ thus statement is equal to $ a(n)-a(n-2)=2.$ Now $ 2.a(n-1)=(-1)^{0}2^{n}\binom{n-1}{0}+(-1)^{1}2^{n-2}\binom{n-2}{1}+(-1)^{2}2^{n-4}\binom{n-3}{2}+\dots$ $ -a(n-2)=(-1)^{1}2^{n-2}\binom{n-2}{0}+(-1)^{2}2^{n-4}\binom{n-3}{1}+(-1)^{3}2^{n-6}\binom{n-4}{2}+\dots$ Since $ (-1)^{0}2^{n}\binom{n-1}{0}=(-1)^{0}2^{n}=(-1)^{0}2^{n}\binom{n}{0},$ $ 2a(n-1)-a(n-2)=(-1)^{0}2^{n}\binom{n}{0}+(-1)^{1}2^{n-2}(\binom{n-2}{1}+\binom{n-2}{0})+(-1)^{2}2^{n-4}(\binom{n-3}{2}+\binom{n-3}{1})+\dots=(-1)^{0}2^{n}\binom{n}{0}+(-1)^{1}2^{n-2}\binom{n-1}{1}+(-1)^{2}2^{n-4}\binom{n-2}{2}+\dots=a(n).$ $ a(1)=2$ and $ a(2)=3.$ Assume that $ a(n)=n+1$ for $ n\le k.$ $ a(k+1)=2a(k)-a(k-1)=2(k+1)-k=k+2.$ So $ a(n)=n+1.$ Thus $ a(n)-a(n-2)=(n+1)-(n-1)=2.$