How Can We Prove a Summation Identity by Double Counting?

[Robb]

Homework Statement

prove the summation by counting in a set two ways.
Mod edit: The summation was later confirmed by the OP to be $\sum_{k = 1}^n 2^{k - 1}$
$$\sum_{n=0}^k 2^{k-1} = 2^{k}-1$$

Homework Equations

The Attempt at a Solution

[/B]
$2^{k-1} = (1+1)^{k-1} = \binom n 0 + \binom n 1 + \binom n 2 + ...+ \binom n n = 2^n$

I assume that if I can show that the LHS = RHS = 2^n, then I have proven they are equivalent? I'm not sure how to deal with the RHS because of the (-1). Using the binomial theorem should I say a = 2^k and b = -1 or do I say (1+1)^{k} - 1, where a = 1 and b = 1. Still not sure how to deal with (-1). Also, I have used the binomial theorem on 2^{k-1} so do I need to use a different method on the RHS. Please advise.

 

[Mark44]

Homework Statement

prove the summation by counting in a set two ways.
Mod edit: The summation was later confirmed by the OP to be $\sum_{k = 1}^n 2^{k - 1}$
$$\sum_{n=0}^k 2^{k-1} = 2^{k}-1$$

Homework Equations

The Attempt at a Solution

[/B]
$2^{k-1} = (1+1)^{k-1} = \binom n 0 + \binom n 1 + \binom n 2 + ...+ \binom n n = 2^n$

I assume that if I can show that the LHS = RHS = 2^n, then I have proven they are equivalent?

You need to show that the LHS and RHS are equal, but they are not equal to 2ⁿ. Also, the expressions in the equation should be shown to be equal, not equivalent, which has to do with statements with the same truth value.

I'm not sure how to deal with the RHS because of the (-1). Using the binomial theorem should I say a = 2^k and b = -1 or do I say (1+1)^{k} - 1, where a = 1 and b = 1. Still not sure how to deal with (-1). Also, I have used the binomial theorem on 2^{k-1} so do I need to use a different method on the RHS. Please advise.

You don't show any relevant equations. Do you know of any that apply in this case? Do you know about geometric progressions?

 

[Robb]

The summation is $\sum_{k=1}^n 2^{k-1}$

 

[Robb]

So, $2^{k-1} = 2 + 2^2 + 2^3 + ... + 2^{n-1}$

I can see this but I'm not sure how to apply it.

 

[Robb]

So, $2^{k-1} = 2 + 2^2 + 2^3 + ... + 2^{n-1}$

I can see this but I'm not sure how to apply it.

Also, $2^k = 2 + 2^2 + 2^3 + ... + 2^{n-1}$

 

[Mark44]

So, $2^{k-1} = 2 + 2^2 + 2^3 + ... + 2^{n-1}$

I can see this but I'm not sure how to apply it.

Also, $2^k = 2 + 2^2 + 2^3 + ... + 2^{n-1}$

No, neither of these is correct.
$2^{k - 1} = 2 \cdot 2 \cdot 2 \dots 2$ where there are k - 1 factors of 2.
Similarly for $2^k$, where there is one more factor of 2.
On the right side of what you wrote is the expansion of $\sum_{k = 1}^{n - 1} 2^k$. This could be written another way by adjusting the index limits and the exponent on 2.
In post 2, I asked if you knew about geometric progressions. Do you?

Edit: The problem asks you to prove the identity in two ways. What two ways do you have to work with? Your textbook or class notes should be helpful here.

 

[Mark44]

Also, in post #1 you started your attempt with this:

3. The Attempt at a Solution
$2^{k-1} = (1+1)^{k-1} = \binom n 0 + \binom n 1 + \binom n 2 + ...+ \binom n n = 2^n$

There are several things wrong here.
$2^{k - 1} \ne 2^n$ unless k - 1 happens to be equal to n
$(1+1)^{k-1} \ne \binom n 0 + \binom n 1 + \binom n 2 + ...+ \binom n n$
Corrected, this would be $(1+1)^{k-1} = \binom {k - 1} 0 + \binom {k - 1} 1 + \binom {k - 1} 2 + \dots + \binom {k - 1} {k - 1}$

 

[Robb]

No, neither of these is correct.
$2^{k - 1} = 2 \cdot 2 \cdot 2 \dots 2$ where there are k - 1 factors of 2.
Similarly for $2^k$, where there is one more factor of 2.
On the right side of what you wrote is the expansion of $\sum_{k = 1}^{n - 1} 2^k$. This could be written another way by adjusting the index limits and the exponent on 2.
In post 2, I asked if you knew about geometric progressions. Do you?

Edit: The problem asks you to prove the identity in two ways. What two ways do you have to work with? Your textbook or class notes should be helpful here.

Yes

 

[Robb]

I think the k-1 exponent is one of the things messing me up. I'm viewing similar to n-1.

 

[Mark44]

I think the k-1 exponent is one of the things messing me up. I'm viewing similar to n-1.

I'm not sure what you mean by this. k - 1 and n - 1 are different.

From post #4:

So, $2^{k-1} = 2 + 2^2 + 2^3 + ... + 2^{n-1}$

It should be obvious that the above is not correct.

It seems to me that you are not understanding the symbols being used, especially in the summation.

$\sum_{k=1}^n 2^{k-1}$
Try expanding this summation with some specific values for n.
What does this expand to when n = 3?
What does this expand to when n = 4?

 

[Robb]

I'm not sure what you mean by this. k - 1 and n - 1 are different.

From post #4:

It should be obvious that the above is not correct.

It seems to me that you are not understanding the symbols being used, especially in the summation.

$\sum_{k=1}^n 2^{k-1}$
Try expanding this summation with some specific values for n.
What does this expand to when n = 3?
What does this expand to when n = 4?

$n = 3: 2^0 + 2^1 + 2^2 = 7$
$n=4: 2^0 + 2^1 + 2^2 +2^3 = 15$

 

[Mark44]

$n = 3: 2^0 + 2^1 + 2^2 = 7$
$n=4: 2^0 + 2^1 + 2^2 +2^3 = 15$

OK, good. The first one is 1 + 2 + 4 = 7 and which happens to equal $2^3 - 1$.
The second is 1 + 2 + 4 + 8 = 15, which happens to equal $2^4 - 1$

I asked a couple of times if you knew about geometric progressions, and I think you said that you did. Do you know how to find the sum of the terms in a geometric progression?

 

[Robb]

Sorry for the delay. Family duties and class!

$S_n = a((1-r^n)/(1-r))$ for the first n terms.

 

[Mark44]

Sorry for the delay. Family duties and class!

$S_n = a((1-r^n)/(1-r))$ for the first n terms.

OK, that's one. Do you know another way? I'm thinking that another way might be induction.

 

[Robb]

$S_{n+1} =\sum_{k=1}^{n+1} 2^{k-1} = 2^{n+1} - 1$
\begin{align} = 2^n - 1 + 2^n
= 2*2^n - 1
= 2^{n+1} - 1\end{align}
As required
Sorry about the first line. Can't figure it out!

 

[Mark44]

Not quite. You need to start with this: $\sum_{k = 1}^n 2^{k - 1}$ and show that it is equal to $2^n - 1$. At least that's what the original problem was supposed to be. Notice that my summation has n terms in it -- your's has n + 1 terms.

You're on the right track, but it needs some tuning.

 

[Mark44]

Sorry about the first line. Can't figure it out!

I fixed it. You mixed braces and parentheses in a couple of places, like this { xxx ). You can't do that.

 

[Robb]

Basis Case:
$n = 1: 2^{1-1} = 2^1 - 1 \Rightarrow$True
$S_n = \sum_{k=1}^n 2^{k-1} = 2^n - 1$
$S_{n+1} = \sum_{k=1}^{n+1} 2^{k-1} = 2^{n+1} - 1$
$S_n = \sum_{k=1}^{n+1} 2^{k-1} = \sum_{k-1}^n 2^n - 1 +2^n$
$= 2*2^n - 1$
$= 2^{n+1} - 1$ as required

I assume you meant I didn't include a basis case.

 

[Mark44]

Basis Case:
$n = 1: 2^{1-1} = 2^1 - 1 \Rightarrow$True
$S_n = \sum_{k=1}^n 2^{k-1} = 2^n - 1$
$S_{n+1} = \sum_{k=1}^{n+1} 2^{k-1} = 2^{n+1} - 1$
$S_n = \sum_{k=1}^{n+1} 2^{k-1} = \sum_{k-1}^n 2^n - 1 +2^n$
$= 2*2^n - 1$
$= 2^{n+1} - 1$ as required

I assume you meant I didn't include a basis case.

No, my comments had to do with your other proof, not this one. Please read what I wrote in post #16.

As for this one, I doubt that your instructor will call it a proof. The following is a copy-and-paste of your work, together with my comments.
1. $n = 1: 2^{1-1} = 2^1 - 1 \Rightarrow$True -- Fine, this is the base case
2. $S_n = \sum_{k=1}^n 2^{k-1} = 2^n - 1$ -- This is the induction hypothesis. You are assuming that this is true, and you should say that.
3. $S_{n+1} = \sum_{k=1}^{n+1} 2^{k-1} = 2^{n+1} - 1$ -- No. You need to show that this step is true, based on the previous step, the induction hypothesis. I don't see anything here that convinces me why this must be true.
4. $S_n = \sum_{k=1}^{n+1} 2^{k-1} = \sum_{k-1}^n 2^n - 1 +2^n$ -- This line shouldn't be here, because it isn't true. It contradicts what you have in the equation in line 2.
$S_n \ne \sum_{k=1}^{n+1} 2^{k-1}$ -- The equation in line 2 shows what $S_n$ equals.