How does the change of variable $\color{red}{r↦n−r}$ transmogrify $\sum\limits_{r=0}^n2^{n-r}\binom{n+r}{n}=2^{2n}$ into $\sum\limits_{k=0}^{n} \frac{\binom{2n-k}{n}}{2^{2n-k}}=1$?
I'm unskilled at performing algebra with Capita-sigma notation. This comment by a deleted user alleges that the "change of variables $\color{red}{r↦n−r}$" will transmogrify $\sum\limits_{r=0}^n2^{n-r}\binom{n+r}{n}=2^{2n}$ into $\sum\limits_{k=0}^{n} \frac{\binom{2n-k}{n}}{2^{2n-k}}=1$.
I got stuck. If I replace $r$ with $\color{red}{n−r}$, then $\sum\limits_{r=0}^n 2^{n-r} \binom{n+r}{n}=2^{2n} \iff \sum\limits_{\color{red}{n−r}=0}^n 2^{n - \color{red}{(n−r)}} \binom{n+\color{red}{(n−r)}}{n}=2^{2n} \iff \sum\limits_{\color{red}{r=n}}^n 2^{\color{red}{r}} \binom{n+\color{red}{(n−r)}}{n}=2^{2n}$
Why can I bring $2^{2n}$ on the RHS into the indexed variable (representing each term of the sum)? On the LHS, $n$ are the lower and upper bounds of summation. So $n$ isn't a Free Variable. I don't know if I'm using "Free Variable" correctly, but what I mean is that because if the RHS were $2^{2x}$, then I can bring $2^{2x}$ into the indexed variable because $x$ never appears in the capital-sigma notation.
1 answer
$n$ is free in the expression $\sum_{r=0}^n 2^{n-r}\binom{n+r}{n}$. The only variable not free in that expression is $r$. What $\sum_{r=0}^n$ means is to treat what comes next as a function of $r$, and compute the sum of that function evaluated at $0$, $1$, and so on up to $n$. If $n$ is used inside that function, its value isn't affected by the $\sum$ notation. The fact that it's used in setting one of the limits of the $\sum$ is irrelevant. So if you are dividing the entire expression by some term involving $n$, it is legal to bring that term inside the summation, because $$ \frac{f(0) + f(1) + \cdots + f(n)}{g(n)} = \frac{f(0)}{g(n)} + \frac{f(1)}{g(n)} + \cdots + \frac{f(n)}{g(n)}$$
The other point I would make is a subtle one, but it trips people up a lot when learning algebra. In a change of variables, you aren't replacing $r$ with $n - r$. You're introducing a new variable $k = n - r$, and then eliminating $r$ using the rules permitted by algebra.
So:
\begin{align} \sum_{r=0}^n 2^{n-r}\binom{n+r}{n} &= 2^{2n} \\ \sum_{r=0}^n 2^k\binom{n+(n - k)}{n} &= 2^{2n} \quad \text{(simple substitution)} \\ \sum_{k=0}^n 2^k\binom{n+(n - k)}{n} &= 2^{2n} \quad \text{($r \in \lbrace 0,\ldots,n\rbrace \Leftrightarrow k \in \lbrace 0,\ldots,n\rbrace$)} \\ \sum_{k=0}^n \frac{2^k\binom{n+(n - k)}{n}}{2^{2n}} &= 1 \quad \text{(divide)} \\ \sum_{k=0}^n \frac{\binom{2n - k}{n}}{2^{2n - k}} &= 1 \quad \text{(tidy up)} \end{align}
0 comment threads
0 comment threads