Udowodnij indukcją matematyczną Requrio:

	n+k n		n+M+1 n+1
Dla k=0 po M ∑		=		, udowodnij podane równanie korzystając z twierdzenia

o indukcji matematycznej oraz własności dwumian Newtona. Z góry dziękuje za pomoc.

jc: Równość wynika z definicji.

	n+M+1 n+1
n+1 elementów ze zbioru {1,2,...,n+M+1} możemy wybrać na		sposobów.

Podzielmy wszystkie wybory wg największego wybranego elementu o wartości k+1. k może przyjmować wartości n, n+1, ..., n+M.

	n+k n
Dla danego k mamy		możliwości wyboru mniejszych

elementów. Sumując otrzymujemy żądaną równość.

Requrio: Preferowałbym praktyczne obliczenia wykorzystujące indukcję zamiast teoretycznych stwierdzeń, łatwiej wtedy zrozumieć.

jc:

	n n		n+1 n+1
Dla M=0, mamy równość		=		.

Załóżmy, że równość zachodzi dla M−1.

	n+M n
Aby przejść z M−1 do M, musimy do obu stron równości dodać		.

	n+M n+1		n+M n		n+M+1 n+1
Wtedy po prawej stronie zobaczymy		+		=		,

czyli to co chcemy. Zgodnie z zasadą indukcji równość zachodzi dla każdego M. −−− Uwaga, dla uproszczenia rachunków zamiast implikacji M ⇒ M+1, pokazałem implikację M−1 ⇒ M.