What is a closed form of the sum:
$$\binom{n}{0}+\binom{n-1}{1}+\binom{n-2}{2}+\binom{n-3}{3}+\cdots$$
A combinatorial proof would also be much appreciated. Any general techniques to solve such sums where the numerator is decreasing and denominator increasing?
On
Any general techniques to solve such sums where the numerator is decreasing and denominator increasing?
A general approach: consider $c_n=\sum\limits_{k=0}^na_{k,n-k}$ for some given family of coefficients $(a_{k,n})$ and assume that, for every fixed $n$, the polynomial $A_n(x)=\sum\limits_{k=0}^na_{k,n}x^k$ is known. Then, $$\sum_{n=0}^\infty A_n(x)x^n=\sum_{k\geqslant0,n\geqslant0}a_{k,n}x^{k+n}=\sum_{n=0}^\infty c_nx^n.$$ In particular, if the generating function on the LHS can be computed, one can hope to recover the value of every $c_n$.
Your case is when $a_{n,k}={n\choose k}$, then the approach outlined above works like a charm...
On
HINT:
The coefficient of $x^n$ in
$$(1+x)^n+x^2(1+x)^{n-1}+x^4(1+x)^{n-2}+\cdots$$ which is a Geometric Series with common ratio $\dfrac{x^2}{1+x}$ which can be safely set in $(-1,1)$ to utilize Infinite Sum formula
On
$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ \begin{align}&\color{#66f}{\large\sum_{k\ =\ 0}^{n}{k \choose n - k}} =\sum_{k\ =\ 0}^{n}\ \overbrace{\oint_{\verts{z}\ =\ 1}% {\pars{1 + z}^{k} \over z^{n - k + 1}}\,{\dd z \over 2\pi\ic}} ^{\ds{=\ \color{#c00000}{k \choose n - k}}} \\[5mm] = &\ \oint_{\verts{z}\ =\ 1}{1 \over z^{n + 1}} \sum_{k\ =\ 0}^{n}\bracks{\pars{1 + z}z}^{k} \,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ 1}{1 \over z^{n + 1}} {\bracks{\pars{1 + z}z}^{n + 1} - 1 \over \pars{1 + z}z - 1} \,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ 1} {\pars{1 + z}^{n + 1} \over \pars{z - r_{-}}\pars{z - r_{+}}} \,{\dd z \over 2\pi\ic} \\[2mm] & -\oint_{\verts{z}\ =\ 1} {1 \over z^{n + 1}\pars{z - r_{-}}\pars{z - r_{+}}} \,{\dd z \over 2\pi\ic}\label{1}\tag{1} \end{align}
where $\ds{r_{\mp} = {-1 \mp \root{5} \over 2}}$ are the roots of $\ds{z^{2} + z - 1 = 0}$. $\ds{r_{-} = -\phi}$ and $\ds{r_{+} = \phi - 1 = {1 \over \phi}}$. $\ds{\phi \equiv {1 + \root{5} \over 2}}$ is the Golden Ratio.
$$ \mbox{Note that}\quad r_{-} < -1\,,\quad 0 < r_{+} < 1.\,\qquad r_{-}r_{+} = r_{-} + r_{+} = -1.\quad r_{+} - r_{-} = \root{5} $$
From expression \eqref{1}: \begin{align}&\color{#66f}{\large\sum_{k\ =\ 0}^{n}{k \choose n - k}} \\[5mm] = &\ {\pars{1 + r_{+}}^{n + 1} \over r_{+} - r_{-}} -{1 \over r_{+} - r_{-}}\oint_{\verts{z}\ =\ 1} {1 \over z^{n + 1}\pars{z - r_{+}}}\,{\dd z \over 2\pi\ic} \\&+ {1 \over r_{+} - r_{-}}\oint_{\verts{z}\ =\ 1} {1 \over z^{n + 1}\pars{z - r_{-}}}\,{\dd z \over 2\pi\ic} \\[5mm]&={\phi^{n + 1} \over \root{5}} -{1 \over \root{5}}\color{#00f}{\oint_{\verts{z}\ =\ 1} {1 \over z^{n + 2}\pars{1 - r_{+}/z}}\,{\dd z \over 2\pi\ic}} \\&-{1 \over \root{5}r_{-}}\color{#c00000}{\oint_{\verts{z}\ =\ 1} {1 \over z^{n + 1}\pars{1 - z/r_{-}}}\,{\dd z \over 2\pi\ic}}\label{2}\tag{2} \end{align}
\begin{align}&\color{#00f}{\oint_{\verts{z}\ =\ 1} {1 \over z^{n + 2}\pars{1 - r_{+}/z}}\,{\dd z \over 2\pi\ic}} =\sum_{k\ =\ 0}^{\infty}r_{+}^{k}\oint_{\verts{z}\ =\ 1} {1 \over z^{n + 2 + k}}\,{\dd z \over 2\pi\ic}=\color{#00f}{0}\label{3}\tag{3} \end{align}
\begin{align}&\color{#c00000}{\oint_{\verts{z}\ =\ 1} {1 \over z^{n + 1}\pars{1 - z/r_{-}}}\,{\dd z \over 2\pi\ic}} =\sum_{k\ =\ 0}^{\infty}{1 \over r_{-}^{k}}\oint_{\verts{z}\ =\ 1} {1 \over z^{n + 1 - k}}\,{\dd z \over 2\pi\ic}={1 \over r_{-}^{n}} =\color{#c00000}{{1 \over \pars{-\phi}^{n}}} \label{4}\tag{4} \end{align}
With \eqref{2}, \eqref{3} and \eqref{4}: \begin{align}&\color{#66f}{\large\sum_{k\ =\ 0}^{n}{k \choose n - k}} ={\phi^{n + 1} \over \root{5}} - {1 \over \root{5}\pars{-\phi}}\, {1 \over \pars{-\phi}^{n}} =\color{#66f}{\large{\phi^{n + 1} + \pars{-1}^{n}\phi^{-n - 1} \over \root{5}}} \end{align} which is the $\ds{\pars{n + 1}}$-Fibonacci Number.
Hint for a combinatorial proof. Count the number of sequences of $1$s and $2$s which add up to $n$.
Method 1. Explain why the number of such sequences which include exactly $k$ $2$s is $\binom{n-k}{k}$.
Method 2. Show that if $a_n$ is the number of sequences then $a_n=a_{n-1}+a_{n-2}$.
Hint for a pictorial proof. $$\def\r{\color{red}{\bullet}}\def\b{\color{blue}{\bullet}}\def\g{\color{green}{\bullet}} \def\w{\circ}\def\s{\ \ \ \ }% \matrix{ \w\cr \w\s\w\cr \w\s\w\s\w\cr \w\s\w\s\w\s\g\cr \w\s\w\s\g\s\b\s\r\cr \w\s\g\s\b\s\r\s\w\s\w\cr \g\s\b\s\r\s\w\s\w\s\w\s\w\cr \b\s\r\s\w\s\w\s\w\s\w\s\w\s\w\cr \r\s\w\s\w\s\w\s\w\s\w\s\w\s\w\s\w\cr}$$ The terms in your expression are the red dots in Pascal's triangle. Each is the sum of the green and blue dots just above it. So the sum of all red dots is equal to the sum of all blue dots plus the sum of all green dots.
See if you can fill in the details. Good luck!