My professor picks the hardest problems

[Jamin2112]

Homework Statement

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 2ⁿ subsets.

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

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

Homework 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)

The Attempt at a Solution

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

A={a₁}
The possible subsets are: {a₁} , {}
So the number of possible subsets are: 2=2¹

A={a₁, a₂}
The possible subsets are: {a₁, a₂} , {a₁}, {a₂}, {}
So the number of possible subsets are: 4=2²

.
.
.
.

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!

 

[Office_Shredder]

So to make the inductive step:

Assume that if |A|=n, then A has 2ⁿ 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.

 

[Mark44]

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 2^k subsets. Now use this assumption to show that a set with n = k + 1 elements has 2^{k + 1} subsets.

It might be helpful to look at why there are 2^k 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.

 

[Jamin2112]

Assume that if |A|=n, then A has 2ⁿ 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?

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={a₁}, where a₁ is a real number. The subsets of A are {} and {a₁}. Since the number of subsets is 2=2¹, the base case n=1 holds.

Now let P(n)=2ⁿ 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.

 

[ephedyn]

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

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.

As suggested:

It might be helpful to look at why there are 2^k 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.

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.

 

[Mark44]

Underlines added.

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.

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 2ⁿ subsets, so P(n) is the statement that a set with n elements has 2ⁿ subsets.

What is the statement P(n + 1)?

 

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

 

[hellofolks]

Jamin2112, please read the private message I sent you.

 

[Jamin2112]

Jamin2112, please read the private message I sent you.

done

 

[Jamin2112]

Underlines added.

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 2ⁿ subsets, so P(n) is the statement that a set with n elements has 2ⁿ subsets.

What is the statement P(n + 1)?

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

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

 

[Jamin2112]

Maybe I'm on to something. If we have a set A_n={a₁, a₂, ..., a_n}, we will have 2ⁿ subsets: {}, {a1}, {a2}, ... , {a₁, a₂, ..., a_n}. Adding 1 more element to A_n 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}, ... , {a₁, a₂, ..., a_n}, {x}, {x, a₁}, {x, a₂}, ..., {a₁, a₂, ..., a_n, x}. The total number of subsets has doubled from from 2ⁿ to 2*2ⁿ=2ⁿ⁺¹.

 

[Office_Shredder]

Maybe I'm on to something. If we have a set A_n={a₁, a₂, ..., a_n}, we will have 2ⁿ subsets: {}, {a1}, {a2}, ... , {a₁, a₂, ..., a_n}. Adding 1 more element to A_n 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}, ... , {a₁, a₂, ..., a_n}, {x}, {x, a₁}, {x, a₂}, ..., {a₁, a₂, ..., a_n, x}. The total number of subsets has doubled from from 2ⁿ to 2*2ⁿ=2ⁿ⁺¹.

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

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

 

[Jamin2112]

I think I got the other problem.

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

Now we wish to show that

P(n)=(qⁿ-1)/(q-1) ----> P(k)=(q^k-1)/(q-1), where k=n+1.

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

 

[Mark44]

I think I got the other problem.

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

Now we wish to show that

P(n)=(qⁿ-1)/(q-1) ----> P(k)=(q^k-1)/(q-1), where k=n+1.

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

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.

 

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

 

[vela]

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.

 

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

 

[hellofolks]

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

 

[Mark44]

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.

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.

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

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.

 

[hellofolks]

Which sections, please?

 

[Office_Shredder]

Every other section listed at physicsforums.com This is in the "Homework and Coursework" section, which is one out of a couple dozen