matematikk.net

Vis at [tex]\sum_{k=0}^m \frac{{m\choose k}}{{n\choose k}}=\frac{n+1}{n+1-m}[/tex] for [tex]n\ge m\ge0[/tex].

Vi viser først et lite lemma. [tex]\sum_{k=0} ^N \frac {(k+a)!} {k!} = \frac {(N+a+1)!} {N! \cdot (a+1)}[/tex] for alle naturlige [tex]N[/tex], [tex]a[/tex], som vises lett ved induksjon ved å legge merke til at, om vi av latskap definerer høyresiden som en funksjon [tex]H(N)[/tex] av [tex]N[/tex] , [tex]H(N+1)-H(N)=\frac {(N+a+1)!} {(N+1)!}[/tex].

Væpnet med lemmaet begynner vi å løse litt opp i summen. Av formelen [tex]{a \choose b }= \frac {a!} {b! \cdot (a-b)!}[/tex] får vi at [tex]\sum_{k=0} ^m \frac {m \choose k} {n \choose k} = \frac {m!} {n!} \sum_{k=0} ^m \frac {(n-k)!} {(m-k)!}=\frac {m!} {n!} \sum_{K=0}^m \frac {(K+n-m)!} {K!}[/tex], der vi i siste trinn summerte 'baklengs', dvs endret summasjonsindeks til [tex]K=m-k[/tex].

Vi bruker så lemmaet vårt og får [tex]\frac {m!} {n!} \sum_{K=0}^m \frac {(K+n-m)!} {K!} = \frac {m!} {n!} \frac {(m+(n-m)+1)!} {m! \cdot (n-m+1)} = {\frac {n+1} {n-m+1}}[/tex], og vi er ferdige.