a) ist die Teilaufgabe b) von Lu's Link.
b) vielleicht so:
Induktionsanfang n=0 klappt: 1=1
Sei nun n∈ℕ ein n, für das die Beh. gilt, dann gilt
$$ \sum_{j=0}^{n+1}{\begin{pmatrix} n+1\\j \end{pmatrix}} $$
Der 1. und der letzte sind je = 1 , also
$$1+ \sum_{j=1}^{n}{\begin{pmatrix} n+1\\j \end{pmatrix}} + 1 $$
und mit der Formel für die Binomialkoeffizienten
$$ =1 +\sum_{j=1}^{n}{(\begin{pmatrix} n\\j \end{pmatrix}+\begin{pmatrix} n\\j-1 \end{pmatrix})} + 1$$
$$ =1+\sum_{j=1}^{n}{\begin{pmatrix} n\\j \end{pmatrix}}+\sum_{j=1}^{n}{\begin{pmatrix} n\\j-1 \end{pmatrix}}+1 $$
und jetzt Indexverschiebung bei der 2. Summe
$$ =1+\sum_{j=1}^{n}{\begin{pmatrix} n\\j \end{pmatrix}}+\sum_{j=0}^{n-1}{\begin{pmatrix} n\\j \end{pmatrix}}+1 $$
jetzt die 1en wieder als ersten bzw. letzten Summanden in die Summe nehmen
$$ =\sum_{j=0}^{n}{\begin{pmatrix} n\\j \end{pmatrix}}+\sum_{j=0}^{n}{\begin{pmatrix} n\\j \end{pmatrix}}$$
Dann Ind.voraussetzung anwenden
= 2n + 2n = 2* 2n = 2n+1 q.e.d.
