# My professor picks the hardest problems

1. Jul 6, 2010

### Jamin2112

1. The problem statement, all variables and given/known data

Or so it seems. Here are 2 that I'm stuck on:

3.11. Use induction on n to prove that a set of n elements has 2n subsets.

3.35. Let q be a real number other than 1. Use induction on n to prove that ∑qi = (qn-1)/(q-1).

[the summation goes from i=0 to n-1]

2. Relevant equations

Proof by induction means proving P(1) is true, and then proving P(n) true ---> P(n+1) true.

(Which I still don't understand completely. It seems like you could just choose a statement P(n) which is true when n=1, and then you're just proving that P(n+1) is true, under the assumption that P(n) is true for all n)

3. The attempt at a solution

A={}
The possible subsets are: {}
So the number of possible subsets are: 1=20

A={a1}
The possible subsets are: {a1} , {}
So the number of possible subsets are: 2=21

A={a1, a2}
The possible subsets are: {a1, a2} , {a1}, {a2}, {}
So the number of possible subsets are: 4=22

.
.
.
.

Okay, so I believe that formula. I know that {} and A are subsets of A, plus the other n-2 possibilities. But I need some sort of formula for P(n), some inequality or summation or something. How do I do this?

The other problem is just hard. ¡Ayudáme, amigos!

2. Jul 6, 2010

### Office_Shredder

Staff Emeritus
So to make the inductive step:

Assume that if |A|=n, then A has 2n subsets for any such set. Now let B have n+1 elements. We can split up B into two subsets, {x} and A where |A|=n (how we choose to do this is irrelevant).

Can you describe the subsets of B in terms of the subsets of A at this point?

The idea of proof by induction is not that you assume a statement is true for all n at the same time, but assume that it's true for a specific n, the value of which could be anything. Then you have to prove that it's true for n+1 at the same time. Basically provide an algorithm so that I can apply it over and over and over again to see that the statement must be true for every natural number by starting off with showing it's true for 1, then explain how I can use that to show it's true for 2, and how I can use that to show it's true for 3, and how I can use that to show it's true for 4 etc.

3. Jul 6, 2010

### Staff: Mentor

For 3.11, you have established that the statement is true for n = 1, so that can serve as your base case. You've also established that it's true for n = 2, which could also serve as the base case.

Now assume that the statement is true for n = k. IOW, assume that a set with k elements has 2k subsets. Now use this assumption to show that a set with n = k + 1 elements has 2k + 1 subsets.

It might be helpful to look at why there are 2k subsets in a set with k elements. First there is the set with no elements, the empty set. Then there all the singleton sets, the sets with one element. Then there are all the sets with two elements, and the sets with three elements, and so on, all the way up to the number of sets with k elements in them.

4. Jul 6, 2010

### Jamin2112

Oh, I see. Tell me whether this makes any sense:

Proof By induction on n.

Let A be the set containing n real real-valued elements. If n=1, A={a1}, where a1 is a real number. The subsets of A are {} and {a1}. Since the number of subsets is 2=21, the base case n=1 holds.

Now let P(n)=2n be the number of subsets for a real-valued set A.

....

Not sure where to go from there. I do need some way show where P(n) comes from---a formula probably involving factorials and stuff.

5. Jul 6, 2010

### ephedyn

Sorry for the messy symbols, I'm at office and don't have time to put everything in LaTeX.

As suggested:

How do we express this in symbols?

Hint 1:

For a set with no elements, this is n C 0
For a set with 1 element, this is n C 0 + n C 1
For a set with k elements, this is n C 0 + n C 1 + ... + n C k i.e. summate n C r from r = 0 to r = k

Hint 2:

Take a look at binomial expansion for the summation.

6. Jul 6, 2010

### Staff: Mentor

There is no mention in the original problem about what sorts of things are in the set, so you should not add an additional assumption about the elements being numbers, let alone real numbers.

The induction hypothesis is that you are assuming that a set with n elements has 2n subsets, so P(n) is the statement that a set with n elements has 2n subsets.

What is the statement P(n + 1)?

7. Jul 6, 2010

### ephedyn

Oh, no. Now that I've gotten home, I realized that I made a pretty elementary mistake:

For a set with no elements, this is 0 C 0
For a set with 1 element, this is 1 C 0 + 1 C 1
For a set with n elements, this is n C 0 + n C 1 + ... + n C n i.e. summate n C r from r = 0 to r = n.

8. Jul 6, 2010

9. Jul 6, 2010

### Jamin2112

done

10. Jul 6, 2010

### Jamin2112

"A set with n+1 elements has 2n+1 (or twice 2n) elements."

Forget the real numbers thing; I don't know what I was thinking.

11. Jul 6, 2010

### Jamin2112

Maybe I'm on to something. If we have a set An={a1, a2, ..., an}, we will have 2n subsets: {}, {a1}, {a2}, ... , {a1, a2, ..., an}. Adding 1 more element to An for a total of n+1 elements gives us all the subsets of the original A plus each element of A with an added n. In other words, if an element x is added to the set A, the subsets of A are now {}, {a1}, {a2}, ... , {a1, a2, ..., an}, {x}, {x, a1}, {x, a2}, ..., {a1, a2, ..., an, x}. The total number of subsets has doubled from from 2n to 2*2n=2n+1.

12. Jul 6, 2010

### Office_Shredder

Staff Emeritus
This is exactly the right idea. So now you've got the inductive step:

If a set with n elements has 2n subsets, a set with n+1 elements has 2n+1 subsets.

13. Jul 6, 2010

### Jamin2112

I think I got the other problem.

Proof By induction on n. The base case n=1 holds:
q0=1=(q1-1)/(q-1).

Now we wish to show that

P(n)=(qn-1)/(q-1) ----> P(k)=(qk-1)/(q-1), where k=n+1.

1 + q + q2 + ... + qn-1 = (qn-1)/(q-1). Adding qn to both sides yields 1 + q + q2 + ... + qn-1 + qn = (qn-1)/(q-1) + qn.The left side is the sum P(n) + qn = P(n+1) and the right side can be rewritten (qn-1+qn+1-qn)/(q-1)=(qn+1-1)/(q-1).Therefore P(k)=(qk-1)/(q-1), as required.

14. Jul 6, 2010

### Staff: Mentor

P(n) is not a function, and it's not a number, so P(n) is not equal to any numeric expression. With induction proofs you have a sequence of statements P(1), P(2), ..., P(n), P(n + 1), ... where each of these represents a statement.

For this problem P(n) is the statement
$$\sum_{i = 0}^{n - 1} q^i = \frac{q^n - 1}{q - 1}$$

(It might be that this is P(n - 1).)
Assume that this statement is true and use it to show that P(n + 1) must be true as well.

15. Jul 6, 2010

### hellofolks

I'm glad you found the answer. This is exactly what I TRIED to explain to you, even though my original message was DELETED. Anyway, however funny that may seem, it looks as though I passed the ideas to you telepathically. Perhaps it's easier to communicate telepathically than through this forum. At least they won't delete my thoughts.

16. Jul 6, 2010

### vela

Staff Emeritus
I saw your posts, and they weren't explanations. They were complete solutions. Posting complete solutions is a violation of the https://www.physicsforums.com/showthread.php?t=414380". That's why they were deleted.

On helping with questions: Any and all assistance given to homework assignments or textbook style exercises should be given only after the questioner has shown some effort in solving the problem. If no attempt is made then the questioner should be asked to provide one before any assistance is given. Under no circumstances should complete solutions be provided to a questioner, whether or not an attempt has been made.

Last edited by a moderator: Apr 25, 2017
17. Jul 6, 2010

### hellofolks

vela, if I were to write a full solution, it would've been much more complete. There were some gaps that needed proving. Anyway, I appreciate that you ranked my drafts as a full solution. But rest assured that, from now on, I'll be giving mediocre tips that are of little or no help, which, by the way, is what many people do here.

18. Jul 6, 2010

### hellofolks

Besides, I believe a forum is meant to hold discussions, not enygmatic half-words.

19. Jul 6, 2010

### Staff: Mentor

Whether or not it was a full solution, it was deemed by a mentor to be close enough to a full solution that it should be deleted.

This section of the forum is for help with homework, and as vela pointed out, it is against the policy of the forum to provide complete answers. Other sections of the forum are devoted to discussions.

20. Jul 6, 2010