0
$\begingroup$

For some reason I found this equation:

$(1 + x)^n - 1 = x \sum\limits_{k=0}^{n-1} (1+x)^k$

I think that this is an identity. If for instance one expands the powers and the sum for n = 4, the polynomials on both sides are identical. I tried to expand the powers using the identity:

$ (1+x)^k = \sum\limits_{s=0}^k \binom{k}{s} x^s 1^{k-s}$

And or to group terms of 0th degree, e.g.

$ (1+x)^n - 1 = \sum\limits_{k=0}^{n-1} \binom{n}{k+1} x^{k+1}$

I'm looking for suggestions rather than a drawn out solution.

$\endgroup$

4 Answers 4

3
$\begingroup$

A combinatorial perspective: (note that since Lagrange interpolation exists, it suffices to prove it for only positive integer $x$.)

Suppose we are coloring a length-$n$ board of squares, or leaving them uncolored. The LHS is the number of ways to do this without leaving the entire board uncolored. Alternatively, we can color the first $k$ and then color the last $n-k$ with the same color, different from that of the $k^\text{th}$ square. If we interpret the $0^\text{th}$ square as being "uncolored", we recover the RHS.

$\endgroup$
2
$\begingroup$

Note that $y^n-1=(y-1)(1+y+y^2+\dots +y^{n-1})$

Now set $y=x+1$

$\endgroup$
1
$\begingroup$

Write $y=(1+x)$ then $(y-1) \sum\limits_{k=0}^{n-1} (y)^k$=$(y-1)\frac{y^n-1}{y-1}=(y^n-1)$ Substituting we have the equality.

$\endgroup$
1
$\begingroup$

It is possible to prove this directly by comparing coefficients of powers of $x$ (though the substitution in the answer by Mark Bennet is probably an easier approach). The coefficient of $x^i$ in $\sum_{k=0}^{n-1}(1+x)^k$ is $\sum_{k=0}^{n-1}\binom ki$ and this can be seen (by an easy induction using Pascal's recurrence for instance) to be $\binom n{i+1}$. The multiplication by$~x$ makes it the coefficient of $x^{i+1}$ in $x\sum_{k=0}^{n-1}(1+x)^k$. Therefore $$ x\sum_{k=0}^{n-1}(1+x)^k = \sum_{i=0}^{n-1}\binom n{i+1}x^{i+1} = \sum_{i=1}^n\binom nix^i = (1+x)^n-1. $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .