# How Can We Prove a Summation Identity by Double Counting?

• Robb
In summary: I'm sorry, I did not understand. I thought the first one was 7?Yes, the first one is 7. So, what is the second one?
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$$

## 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.

Last edited by a moderator:
Robb said:

## 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$$

## 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 2n. 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.
Robb said:
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?

Last edited:
The summation is ##\sum_{k=1}^n 2^{k-1}##

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 said:
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}##

Robb said:
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.

Last edited:
Also, in post #1 you started your attempt with this:
Robb said:
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}##

Mark44 said:
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

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

Robb said:
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?

Mark44 said:
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##

Robb said:
##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?

Sorry for the delay. Family duties and class!

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

Robb said:
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.

##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!

Last edited by a moderator:
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.

Greg Bernhardt
Robb said:
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.

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.

Robb said:
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.

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.

## 1. What is the purpose of counting a set in two ways?

The purpose of counting a set in two ways is to verify the accuracy of the total count. By counting the same set in two different ways, you can catch any errors or discrepancies in the counting process.

## 2. How do you count a set in two ways?

To count a set in two ways, you can use different methods such as grouping, partitioning, or using a visual representation like a diagram or chart. The key is to ensure that both counts are done using the same elements and are not overlapping.

## 3. What are some benefits of counting a set in two ways?

Counting a set in two ways can help improve accuracy, identify errors, and enhance understanding of the set. It can also be a useful tool for problem-solving and critical thinking skills.

## 4. Can you provide an example of counting a set in two ways?

Sure, let's say we have a set of 10 apples. We can count them in two ways: 1) grouping them into sets of 2 and counting the number of groups (5 groups of 2 apples each), and 2) arranging the apples into a 4x3 grid and counting the total number of apples (12 apples). Both methods result in a count of 10 apples.

## 5. How does counting a set in two ways relate to mathematical concepts?

Counting a set in two ways is related to mathematical concepts such as the commutative and associative properties, which state that the order or grouping of elements does not affect the total count. It also relates to the concept of equivalence, where two different representations of the same quantity are considered equal.

• Calculus and Beyond Homework Help
Replies
6
Views
655
• Calculus and Beyond Homework Help
Replies
17
Views
1K
• Calculus and Beyond Homework Help
Replies
14
Views
2K
• Calculus and Beyond Homework Help
Replies
11
Views
1K
• Calculus and Beyond Homework Help
Replies
4
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
571
• Precalculus Mathematics Homework Help
Replies
11
Views
526
• Calculus and Beyond Homework Help
Replies
6
Views
1K
• Calculus and Beyond Homework Help
Replies
3
Views
708
• Calculus and Beyond Homework Help
Replies
4
Views
1K