2 Variable induction on a summation

Question

I'm trying to prove this is true: $$\sum_{i=1}^{k} 2^{i-1}(k-i) = 2^k-k-1$$

I'm used to doing normal inductions on summations, but this one is a little confusing to me. Basically, because both i and k are present in the equation itself am I supposed to ensure that both i goes to k+1 and and k also goes to k+1? Does it matter if you start with inducting on k or i first?

I've tried an induction where I induct on i first:

$$\sum_{i=1}^{k+1} = \sum_{i=1}^{k} + 2^{k+1-1}(k-(k+1)) = 2^k-k-1+2^k(-1)=-k-1$$

Obviously this isn't what I want since I want the end goal to look like:

$$2^{k+1}-(k+1)-1 $$

Additionally if anyone knows of any places where I could find example problems of summations using two variables I'd love to know.

Answer 1

Put $$ S(k) = \sum\limits_{i\, = \,1}^k {2^{\,i - 1} \left( {k - i} \right)} \quad \quad F(k) = 2^{\,k} - k - 1 $$ so you shall demonstrate by induction that $$ S(k) = F(k) $$

Then clearly the induction is on varying the $k$, while the $i$ is just a parameter internal to $S$.

Now

• the identity is true for $k=1$ $$ S(1) = \sum\limits_{i\, = \,1}^1 {2^{\,i - 1} \left( {1 - i} \right)} = 0 = F(1) = 0 $$
• if the identity is true for $k$ then it is true for $k+1$, because we have $$ \eqalign{ & S(k + 1) = \sum\limits_{i\, = \,1}^{k + 1} {2^{\,i - 1} \left( {k + 1 - i} \right)} = \cr & = \sum\limits_{i\, = \,1}^{k + 1} {2^{\,i - 1} \left( {k - i} \right)} + \sum\limits_{i\, = \,1}^{k + 1} {2^{\,i - 1} } = \cr & = \sum\limits_{i\, = \,1}^k {2^{\,i - 1} \left( {k - i} \right)} + 2^{\,k} \left( { - 1} \right) + {{1 - 2^{\,k + 1} } \over {1 - 2}} = \cr & = S(k) - 2^{\,k} + 2^{\,k + 1} - 1 = S(k) + 2^{\,k} - 1 \cr} $$ and $$ \eqalign{ & F(k + 1) = 2^{\,k + 1} - k - 1 - 1 = 2^{\,k} + 2^{\,k} - k - 1 - 1 = \cr & = F(k) + 2^{\,k} - 1 \cr} $$

That's all what needed to give the proof by induction

Answer 2

The $i$ in your formula is an auxiliary variable or index to express the sum with the $\sum$ notation instead of using $\cdots$. Consider another example (so you can then try with yours): $$\sum_{i=1}^{k}(2i-1)=k^2,\:k\in \mathbb N. \qquad (1)$$ Here $\sum_{i=1}^{k-1}(2i-1)$ is a more compact (and perhaps more formal and precise) notation for the $k$-termed sum $$(2\cdot \underline1-1)+(2\cdot \underline2-1)+(2\cdot \underline3-1)+\cdots+(2\cdot (\underline{k-1})-1)+(2\cdot \underline k-1).$$ Note that each term is $2i-1$ but in the first one $i$ has been replaced by $1$, then by $2$, and so on until $k$ (these numbers are underlined in the previous equation).

And more important for our discussion: there's no such thing as $i$ in this last equation. It's disappeared, even when the original expression had such 'variable'.

But as I've said, that's just an auxiliary symbol. Think that it could even be replaced for something like $\bigcirc$, as in $\sum_{\bigcirc=1}^{k}(2\cdot\bigcirc-1)$.

So now, you can use that 'expanded' expression for your proof by induction. When you feel more comfortable with the $\sum$ sign, you can even work with its properties and avoid the expanded expressions with $\cdots$.

In our case, first note that when $k=1$ we have that $(1)$ becomes $$\sum_{i=1}^{1}(2i-1)=1^2.\qquad (2)$$ The expression on the right side is obviously equal to $1$. Now, on the left side we have a sum in which the index $i$ varies from $1$ to $1$: that is, there is only one term (no actual sum) which is $2i-1$ but taking $i=1$. So on the left we have $2\cdot 1-1=1$, and so $(2)$ is true.

Then, for the inductive step we need to prove that if $(1)$ holds when $k=h$, that is $$\sum_{i=1}^{h}(2i-1)=h^2,$$ then it also holds when $k=h+1$, which means $$\sum_{i=1}^{h+1}(2i-1)=(h+1)^2.$$

Note that I did not replace the $i$'s. The induction happens in the variable that really is a variable to which we can assign the value that we want. We could actually have worked without $\sum$ and say that we want to prove that if $$(2\cdot \underline1-1)+(2\cdot \underline2-1))+\cdots+(2\cdot (\underline{h-1})-1)+(2\cdot \underline h-1)=h^2$$ holds, then also $$(2\cdot \underline1-1)+(2\cdot \underline2-1)+\cdots+(2\cdot (\underline{h-1})-1)+(2\cdot \underline h-1)+(2\cdot (\underline{h+1})-1)=(h+1)^2$$ does.

For a proof of this fact consider that in the last expression the terms on the left from the first one until the next to last one add up to $h^2$ (that's the inductive hypothesis), so $$(2\cdot 1-1)+(2\cdot 2-1)+\cdots+(2\cdot (h-1)-1)+(2\cdot h-1)+(2\cdot (h+1)-1)=$$$$=h^2+(2\cdot (h+1)-1)=h^2+2h+1=(h+1)^2,$$ and this completes the proof.

The same can be expressed with $\sum$ notation, if we consider that doing the sum with $i$ going from $1$ to $h+1$ is equivalent to do it with $i$ from $1$ to $h$ and then adding the term corresponding to $i=h+1$. Then it would be the same: $$\sum_{i=1}^{h+1}(2i-1)=\sum_{i=1}^h(2i-1)+(2\cdot (h+1)-1)=h^2 +(2\cdot (h+1)-1)=(h+1)^2.$$