Wykaż, że średnia arytmetyczna

[max123321]

Rozważamy wszystkie \(\displaystyle{ k}\)-elementowe podzbiory zbioru \(\displaystyle{ \left\{ 1,...,n\right\},k>0}\).
W każdym podzbiorze wybieramy najmniejszą liczbę. Wykaż, że średnia arytmetyczna tych liczb jest równa \(\displaystyle{ \frac{n+1}{k+1}}\).

Jak to zrobić? Jakaś wskazówka?

[Premislav]

Wskazówka: niech \(\displaystyle{ i\in\left\{ 1, \ldots n\right\}}\). Policz, ile jest \(\displaystyle{ k}\)-elementowych podzbiorów zbioru \(\displaystyle{ \left\{ 1, \ldots n\right\}}\), w których \(\displaystyle{ i}\) jest najmniejszym elementem (tak naprawdę jakikolwiek podzbiór będzie spełniał taką własność tylko gdy \(\displaystyle{ i\le n-k+1}\)). W tym celu do naszej liczby \(\displaystyle{ i}\) dobierasz \(\displaystyle{ k-1}\) spośród \(\displaystyle{ n-i}\) liczb ze zbioru \(\displaystyle{ \left\{ i+1, \ldots n\right\}}\).-- 9 mar 2019, o 19:20 --Do udowodnienia pozostaje tożsamość:
\(\displaystyle{ \frac{1}{{n\choose k}} \sum_{i=1}^{n-k+1}i{n-i \choose k-1} =\frac{n+1}{k+1}}\)

To zadanie ma też ładniejsze rozwiązanie, ale nie pamiętam go.

[max123321]

Tak, racja, zrozumiałem tą równość i zgadzam się, że ona pozostaje do udowodnienia. Ale jak ją udowodnić? Ja próbowałem indukcyjnie, ale nie wiem jak skorzystać z założenia indukcyjnego, bo z uwagi na to \(\displaystyle{ i}\), nie mogę wyciągnąć przed nawias tego wyrażenia: \(\displaystyle{ \frac{1}{{n\choose k}} \sum_{i=1}^{n-k+1}i{n-i \choose k-1}}\). Jak zatem sobie poradzić?

[Premislav]

O, mam pomysł:
przekształcamy równoważnie tezę, czyli równość
\(\displaystyle{ \frac{1}{{n\choose k}} \sum_{i=1}^{n-k+1}i{n-i \choose k-1}=\frac{n+1}{k+1}}\)
do postaci
\(\displaystyle{ \sum_{i=1}^{n-k+1}i{n-i \choose k-1} ={n+1 \choose k+1}}\)
Oto dowód tej ostatniej równości:
wyjdźmy od znanej tożsamości
\(\displaystyle{ \sum_{j=k}^{m}{j \choose k}={m+1\choose k+1}}\),
której dowód to prosta interpretacja kombinatoryczna (indukcją po \(\displaystyle{ m\ge k}\) też łatwo idzie).
W szczególności
\(\displaystyle{ \sum_{j=k-1}^{n-1}{j \choose k-1}={n \choose k}}\)
a my chcemy policzyć (\(\displaystyle{ j:=n-i}\))
\(\displaystyle{ \sum_{j=k-1}^{n-1}(n-j){j \choose k-1}=\\= \sum_{j=k-1}^{n-1}((n+1)-(j+1)){j\choose k-1}=\\=(n+1) \sum_{j=k-1}^{n-1}{j \choose k-1}-k \sum_{j=k-1}^{n-1}\frac{j+1}{k}{j\choose k-1}=\\=(n+1){n\choose k}-k{n+1\choose k+1}={n+1\choose k+1}}\)
Po drodze korzystam kilka razy z następującej, bardzo przydatnej własności:
\(\displaystyle{ (n+1){n\choose k}=(k+1){n+1\choose k+1}}\)

Sorry, że tak rachunkowo, ale nie umiem kombinatoryki.