I have solved a counting problem and I obtained the sum $$\sum_{k=0}^n \binom{(n+1)-k}{k}.$$
However, this is unsatisfactory to me because I would like an explicit formula. Does anyone know if this is, or is similar, to a famous counting identity? I cannot find it anywhere.
Thank you in advance.
On
I do not think that this is an answer since based on observation.
I generated a table of $$S_n=\sum_{k=0}^n \binom{(n+1)-k}{k}$$ and starting form $n=1$, obtained $$2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711$$ Looking at $OEIS$, I found sequence $A000045$ which seems to have been extensively worked.
From the link it seems that the simplest closed form formula is $$S_n=\frac{ \left(\left(1+\sqrt{5}\right)^{n+2}-\left(1-\sqrt{5}\right)^{n+2}\right)}{2^{n+2}\sqrt{ 5}}=\text{Round}\left[\frac{\phi ^{n+2}}{\sqrt{5}}\right]$$
On
It is possibile to prove that $$\sum_{k\geq0}\dbinom{n-k}{k}=F_{n+1} $$ by induction, where $F_{n} $ is the $n-$th Fibonacci number. In particular the inductive step is $$\begin{align}\sum_{k\geq0}\dbinom{n+1-k}{k}= & \sum_{k\geq0}\dbinom{n-k}{k}+\sum_{k\geq0}\dbinom{n-k}{k-1} \\ = & \sum_{k\geq0}\dbinom{n-k}{k}+0+\sum_{k\geq1}\dbinom{n-1-k+1}{k-1} \\ = &\sum_{k\geq0}\dbinom{n-k}{k}+\sum_{k\geq0}\dbinom{n-1-k}{k} \\ = &F_{n+1}+F_{n} \\ = & \color{red}{F_{n+2}}. \end{align}$$
$\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{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ Lets $\ds{a_{n} \equiv \sum_{k = 0}^{n}{n + 1 - k \choose k}\,,\quad \mbox{Note that}\ a_{0} = 1\ \mbox{and}\ a_{1} = 2}$.
\begin{align} a_{n} & = \sum_{k = 0}^{n}{n + 1 - k \choose k} = \sum_{k = 0}^{n}{n - k \choose k} + \sum_{k = 1}^{n}{n - k \choose k - 1} = \\[5mm] & = \sum_{k = 0}^{n}{n - k \choose k} + \sum_{k = 0}^{n - 1}{n - k - 1 \choose k} \\[5mm] & = \bracks{{n - n \choose n} + \sum_{k = 0}^{n - 1}{n - k \choose k}} + \bracks{{n - \bracks{n - 1} - 1 \choose n - 1} + \sum_{k = 0}^{n - 2}{n - 1 - k \choose k}} \\[5mm] & = \delta_{n0} + \delta_{n1} + a_{n - 1} + a_{n - 2} \end{align} Then, $$ \left\lbrace\begin{array}{rcl} \ds{a_{0}} & \ds{=} & \ds{1} \\ \ds{a_{1}} & \ds{=} & \ds{2} \\ \ds{a_{n}} & \ds{=} & \ds{a_{n - 1}\ +\ a_{n - 2}\,,\quad n \geq 2} \end{array}\right. $$ These relations show that \begin{align} a_{n} & = \color{#f00}{\sum_{k = 0}^{n}{n + 1 - k \choose k}} = F_{n + 2} = \color{#f00}{{\pars{1 + \root{5}}^{n + 2} - \pars{1 - \root{5}}^{n + 2} \over 2^{n + 2}\root{5}}} \end{align} $\ds{F_{n}}$ is a Fibonacci Number.