Prove by induction: the coefficients of (a+b) to the power of n are the same if turned into a number as 11 to the power of n

Question

Proof by induction that the coefficients of $(a+b)^n$ in order, if place as a number, the first coefficient being having the biggest place value, and each number lowers in place value, are equal to the of $11^n$

So far I have got:

I rewrote the equation as $11^n =$ $\sum_{r=0}^{n} \binom{n}{r} * 10^{(n-r)}$ then tested the case for n=1 and got $$11^1 =$$ $$\sum_{r=0}^{1} \binom{1}{r} * 10^{(1-r)}$$ which is true 11 = 11

then I assumed the case is true for k. However, when I get to the part where I have to prove that it is true for k+1 I get stuck. Please help

Answer 1

The statement is not completely true, as I'll get to at the end of my answer.

Let's break down $11^n$ as $(10 + 1)^n$. By the Binomial Theorem:

$11^n = (10 + 1)^n = 10^n*\binom{n}{n} + 10^{n-1}*1*\binom{n}{n-1} + ... + 10^{0}*1*\binom{n}{0}$

which if we write as a sum from right to left:

$11^n = \sum_{k = 0}^n 10^{k}\binom{n}{k}$

The digits of a number are basically the coefficients in the decimal representation of that number, example:

$1234 = 1*10^3 + 2*10^2 + 3*10^3 + 4*10^4$

so the "digits" of $11^n$ are the coefficients of the powers of 10 in that expression, which are the same as the binomial coefficients for any expression $(a+b)^n$. View Binomial Theorem

Why do I have "digits" in quotes?

Because after n = 4, the binomial coefficients are more than single digits (i.e. 10 or more), so they "carry over" to form the digits of $11^n$

$11^5 = (10+1)^5 = 10^5 + 5*10^4 + 10*10^3 + 10*10^2 + 5*10 + 1$

So we have 1 5 10 10 5 1 as the coefficients, which collapses to 161051 if you treat each number as a digit from right to left. (100000 + 50000 + 10000 + 1000 + 50 + 1)

---

Coming back to your induction case, let's assume:

$11^k = \sum_{r=0}^k \binom{k}{r} * 10^{(k-r)}$

Note that as $\binom{k}{r} = \binom{k}{k-r}$, we can do some quick substitution k-r = q and rewrite the sum as:

$11^k = \sum_{q=0}^k \binom{k}{q} * 10^q$

Multiplying both sides by 11:

$11^{k+1} = (10 + 1) * \sum_{q = 0}^k \binom{k}{q} * 10^q$

$ = 10*\sum_{q = 0}^k \binom{k}{q} * 10^q + \sum_{q = 0}^k \binom{k}{q} * 10^q$

$ = \sum_{q = 0}^k \binom{k}{q} * 10^{q+1} + \sum_{q = 0}^k \binom{k}{q} * 10^q$

We have to get k+1 in both expressions. So let's force it, that's the beauty of induction. Let q + 1 = z. We also know that

$ = \sum_{z = 1}^{k+1} \binom{k}{z - 1} * 10^{z} + \sum_{q = 0}^k \binom{k}{q} * 10^q$

By multiplying and dividing by z & k - z + 1, we know that $\binom{k + 1}{z} = \binom{k}{z-1} * \frac{k+1}{z}$

Also, $ \binom{k+1}{q} = \binom{k}{q} * \frac{k+1}{k - q +1} $

So our expression becomes

$= \sum_{z = 1}^{k+1} \binom{k+1}{z}* \frac{z}{k+1} * 10^{z} + \sum_{q = 0}^k \binom{k+1}{q} * \frac{k-q+1}{k+1} * 10^q$

Now, if you take the q = 0 term away from the second sum, and the z = k+1 term away from the first sum we have two sums, both running from 1 to k. At this point it's important to point out "z" and "q" are just variables used for notation, what really matters for the sums are the ranges (1 to k+1) and the functions being added.

So we can just merge the two sums (and add 1 as the q = 0 term is equal to 1, and add $10^{k+1}$ as that is the value of the z = k+1 term)

So we have:

$1 + 10^{k+1} \sum_{z = 1}^{k} \binom{k+1}{z}* \frac{z}{k+1} * 10^{z} + \binom{k+1}{z} * \frac{k-z+1}{k+1} * 10^z$

= $1 + 10^{k+1} \sum{z = 1}^{k} \binom{k+1}{z} * 10^{z} * \frac{z + k - z + 1}{k+1}$

= $1 + 10^{k+1} + \sum{z = 1}^k \binom{k+1}{z} * 10^{z}$

= $\sum_{z = 0}^{k+1} \binom{k+1}{z} * 10^{z}$

Which is what we wanted to arrive at by Induction

Answer 2

I agree that $$11^n = \sum_{r=0}^n \binom nr 10^{n-r} \tag 1$$ is a good interpretation of the problem statement. The problem statement is a little bit ambiguous, but I read "lowers in place value" as "has place value exactly one place lower", and I assume that the last coefficient has the lowest place value, $10^0$. There is a little further interpretation required, which is what do we do about the coefficients that have more than one digit, but my interpretation is that we're supposed to just add up the numbers as shown on the right-hand side of Equation $(1)$. For example, for $n = 5$, the right-hand side of Equation $(1)$ is \begin{align} \binom50 10^5 + \binom51 10^4 &+ \binom52 10^3 + \binom53 10^2 + \binom54 10^1 + \binom55 10^0 \\ &= 1 \cdot 10^5 + 5 \cdot 10^4 + 10 \cdot 10^3 + 10 \cdot 10^2 + 5 \cdot 10^1 + 1 \cdot 10^0 \\ &= 100000 + 50000 + 10000 + 1000 + 50 + 1 \\ &= 161051. \end{align} Yes, the non-zero digits of $5 \cdot 10^4$ and $10 \cdot 10^3$ combine to make a digit $6$ in the result rather than a $5$ followed by a $1$, but the problem statement did not explicitly say this could not happen. If the digits of the coefficients were meant to be kept separate and only concatenated, never added together, one might expect the problem statement to be a little less insistent on corresponding each coefficient to "a" place value. (When multiple-digit numbers are concatenated, each occupies multiple places and does not have "a" place value.)

Now consider that for any integer $r$, it is always true that $1^r = 1$. So we can write $$\sum_{r=0}^n \binom nr 10^{n-r} = \sum_{r=0}^n \binom nr 10^{n-r} 1^r. \tag2 $$

I will stop writing formulas now so as not to spoil the surprise when you figure out what the right-hand side of Equation $(2)$ is, but here is a hint: when you use the binomial theorem to expand $(a+b)^n$, what do you get?