Proving polynomial relationship using combinations

Question

Generalize the polynomial relationship $$(1+x)^n=\sum_{k=0}^n x^k {n \choose k}$$ for all positive integers $n$ to $$(a+x)^n$$

My work so far:

I want to use proof by induction to prove this. I am trying to find a polynomial to plug in for $x$ so that this relationship is satisfied. Proving the base case, however, $n=0$ will yield always yield a result of $1=1$. So our base case is satisfied. Additionally, the case for $n=1$ will yield $x+a$, so I must find a polynomial raised to the first power plus one that will result in $x+a$. That polynomial is $x+a-1$. My goal now is to prove this equality.

$$(a+x)^n=\sum_{k=0}^n (a+x-1)^k {n \choose k}.$$

I've already shown the base case is satisfied; now I will solve for the example for $n+1$ $$(a+x)^{n+1}=\sum_{k=0}^{n+1} (a+x-1)^k {n+1 \choose k}$$ $$(a+x)^n(a+x)=\sum_{k=0}^n (a+x-1)^k {n \choose k} + (a+x-1)^{n+1}{n+1 \choose k}$$.

At this point, I get lost and don't know where to continue from here. I assume there's something I have to do with Pascal's rule, but I don't see where that will lead me.

Answer 1

You know $$(1+x)^n=\sum_{k=0}^n {n \choose k}x^k$$

Thus

$$(a+x)^n = a^n(1+\frac {x}{a})^n=$$

$$ a^n\sum_{k=0}^n{n \choose k} (\frac {x}{a})^k =$$

$$\sum_{k=0}^n{n \choose k} x^k a^{n-k} $$

Answer 2

Imagine you have a set with $n$ elements and $0\le k \le n$. There are $n\choose k$ subsets of size $k$. Now pick an element of the set and call it $x$. You can get a subset of size $k$ two ways

$k$ not allowed (choose all $k$ from the $n - 1$): ${n-1\choose k}$ ways

$k$ included (choose $k-1$ from the remaining $n-1$: ${n-1\choose k-}|$.

Therefore

$${n\choose k} = {n-1 \choose k-1} + {n-1 \choose k}. $$

This is the key.