Thread: help showing simple induction

For each natural number n>0, we define the set B_n to be {2^i:i in ℕ and 0<=i<n}

My inductive definition for B_n is
∀n∈ℕ+B_n={2^0,2^1,2^2,…,2^(n-1)}={B_(n-1)}∪{2^(n-1)}


My proof that for any natural number n>0 if t∈ℕ and 0<=t<2^n , then there is a subset A of B_n such that ∑[x∈A]x=t.







[Base Case]:
Prove P(1)
Let n=1
Then t∈ℕ s.t 0≤t<2^1
So t∈{0,1}
∅⊂B_1 ∑[x∈∅]x = 0
{2^0}⊂B_1 ∑[x∈{2^0}]x = 1
∴∀t∈ℕ s.t 0≤t<2^1 ∃ A⊆B s.t ∑[x∈A]x = t

[I.S]:
Let n≥2
Suppose P(n) [I.H]
W.T.P P(n+1) i.e. t∈ℕ s.t 0≤t<2^(n+1) → ∃ subset A s.t A⊆B_(n+1) ˄ ∑[x∈A]x = t

t∈ℕ s.t 0≤t≤2^(n)-1 → ∃ subset A s.t A⊆B_n ˄ ∑[x∈A]x = t [re-arranging inequality]
For n
C1:
0≤t≤2^(n-1)-1 [since t∈ℕ, n≥2] (*) [re-arranging inequality]

C2:
2^(n-1)-1<t≤2^(n)-1 [since t∈ℕ, n≥2] (**) [re-arranging inequality]
For n+1
C1:
0≤t≤2^(n-1+1)-1 [since t∈ℕ, n≥2] (***) [by I.H, since ***=*+**]

C2:
2^(n-1+1)-1<t≤2^(n+1)-1 [since t∈ℕ, n≥2] [by I.H]
0≤t<2n+1 as wanted.






Is this right and formal?

Originally Posted by Sneaky

My inductive definition for B_n is
∀n∈ℕ+B_n={2^0,2^1,2^2,…,2^(n-1)}={B_(n-1)}∪{2^(n-1)}

An inductive definition needs a base case (B_1).

For the proof, it's good to say that induction is on n (not on t).

[Base Case]:
Prove P(1)

P was not defined above.

Let n=1
Fix (consider) t∈ℕ s.t 0≤t<2^1

{2^0}⊆B_1 ∑[x∈{2^0}]x = 1

[I.S]:
Let n≥2
Suppose P(n) [I.H]
W.T.P P(n+1) i.e. t∈ℕ s.t 0≤t<2^(n+1) → ∃ subset A s.t A⊆B_(n+1) ˄ ∑[x∈A]x = t

What is W.T.P.: Want To Prove? Also, write "Case 1" instead of "C1."

t∈ℕ s.t 0≤t≤2^(n)-1 → ∃ subset A s.t A⊆B_n ˄ ∑[x∈A]x = t

This is the induction hypothesis.

After that, it became too hard to understand. Are you claiming these facts or are you going to prove them? What does "for n" mean? Rearranging which inequality? A formal proof does not have to be difficult to read.

My inductive definition for B_n is now:






∀n∈ℕ^+ B_n={2^0,2^1,2^2,…,2^(n-1)}={B_(n-1)}∪{2^(n-1)}
B_1={2^0}
t∈ℕ s.t 0≤t≤2^(n)-1 → ∃ subset A s.t A⊆B_n ˄ ∑[x∈A]x = t
-------------------------------------------------------------



Let P(n) be the predicate that ∀n∈ℕ+, t∈ℕ s.t 0≤t<2^n → ∃ subset A s.t A⊂B_n ˄ ∑[x∈A]x = t.


This is P(n)

btw when it says A of B_n, does that mean subset or proper subset?
-------------------------------------------------------------



w.t.p is Want.To.Prove
--------------------------------------------------------------


after this i am explaining this:


Suppose P(n) for all n >= 2, then

0≤t<2^n
can become
0≤t≤2^(n) - 1


then


there exists at least 1 t s.t 0≤t≤2^(n-1)-1 (*)

there exists at least 1 t s.t 2^(n-1)-1≤t≤2^(n)-1 (**)



since


0 ≤ 2^(n-1)-1 < 2^(n)-1
since t∈ℕ and n>=2
One of my problems here is that i can't prove (**)




i think the key to this proof is to split the cases into 2.
the * case for n+1 is basically the union of the * and ** for n (i don't know if you understand what i wrote)

if n=1, t is 0 and 1, which i proved in the base case
if n=2, by * there is at least 1 t in {0,1}, this is true since i proved it in base case
by ** there is at least 1 t in {2,3}, (this is the part i can't prove)

if i prove **, then it can be easier to show that for the other n's, * is proved by the (n-1)'s * and ** being proved.
This is what i want to get at to solve this. Like before i dont know how to write this as well (assuming ** gets proved).




And what do you mean by fix(consider) ?

I'll mark with red what needs to be removed.

Let P(n) be the predicate that ∀n∈ℕ+, t∈ℕ s.t 0≤t<2^n → ∃ subset A s.t A⊂B_n ˄ ∑[x∈A]x = t.

btw when it says A of B_n, does that mean subset or proper subset?

I am not sure where it says "A of B_n." I believe it should be improper subset everywhere.

Suppose P(n) for all n >= 2, then

0≤t<2^n
can become is equivalent to
0≤t≤2^(n) - 1

there exists at least 1 t s.t 0≤t≤2^(n-1)-1 (*)

Of course: take t = 0.

there exists at least 1 t s.t 2^(n-1)-1≤t≤2^(n)-1 (**)

Take t = 2^(n-1)-1.

What you probably want to say is that if 0 <= t < 2^n, then either 0 <= t < 2^(n-1), or 2^(n-1) <= t < 2^n.

since


0 ≤ 2^(n-1)-1 < 2^(n)-1
since t∈ℕ and n>=2

I am lost with two words "since" in a row. I don't understand where one sentence ends and another begins.

Suppose P(n) is true and let 0 <= t < 2^(n+1). Then either 0 <= t < 2^n or 2^n <= t < 2^(n+1). In the first case, the induction hypothesis states that t is represented as a sum of some of 2^0, ..., 2^(n-1) (the last element of B_(n+1), i.e., 2^n, is not used). In the second case, 0 <= t - 2^n < 2^n, so t - 2^n is represented as a sum of 2^0, ..., 2^(n-1) by IH; then we add 2^n to that sum to get t.

And what do you mean by fix(consider) ?

A proof of a statement "For all x..." typically starts with "Fix (or consider) an arbitrary x..."

In the future, please make an extra effort to write clearly: capitalize the first word in each sentence, use periods to terminate sentences, avoid unnecessary abbreviations, etc.

Can you please explain in more detail about your two cases. I don't understand what you mean.

Do you understand that 0 <= t < 2^(n+1) implies 0 <= t < 2^n or 2^n <= t < 2^(n+1)? If yes, then which specific part you don't understand?

OK I think I understand now, is this right and formal?

modified:


But one thing I am not sure about is, that you started proving P(n) but started with P(n+1), aren't we supposed to start from P(n) and get to P(n+1) ?

Yes, I think this is correct. I only have some stylistic remarks.

Every time you state P(n) (in the problem statement, in the definition of P(n) and after "W.T.P"), it starts with "t ∊ ℕ s.t ..." (by the way, if you have a period after s in "s.t", then you should also have one t, and similarly for W.T.P, which is not a universally accepted abbreviation). When a new variable (t in this case) is introduced, it should be bound by a universal or existential quantifier. In this case, I would say, "For all t ∊ℕ, if 0 <= t < 2^n, then ..." or "For all t ∊ℕ s.t. 0 <= t < 2^n, it is the case that ..." In fact, the claim to prove should start with "for all n > 0"; so far you only have it in the definition of B_n. It is not necessary to write "subset A" since you immediately write A ⊆ B_n.

Remove the sentence "If 0 <= t < 2^(n+1), then..." from the second line of the proof. First, n-1 should be replaced with n in the conclusion and, second, its place is later, in the induction step.

It's good that you use explicit universal quantifier with t at the end of the base case.

Remove "since t ∊ℕ, n >= 2" from the induction step. It is enough to write n >= 2 once at the beginning if the induction step.

In Case 2, t - 2^n is represented as a sum of numbers from B_n by the IH, and is it t, not t - 2^n, that equals 2^n plus that sum.

I would remove the last line: it is not clear what "t is existent" means, and you were proving P(n+1), not P(n).

Originally Posted by Sneaky

But one thing I am not sure about is, that you started proving P(n) but started with P(n+1), aren't we supposed to start from P(n) and get to P(n+1) ?

I am not exactly sure what you mean by "started proving P(n)." By "started with P(n+1)," do you mean that I started proving the induction step by considering an arbitrary t such that 0 <= t < 2^(n+1), which is the premise of P(n+1)? If P(n) were an equation, then yes, formally one should start with that equation and gradually rewrite it to get P(n+1). In this case, P(n+1) has the form of an implication, so we start proving it like any other implication, by assuming the premise. We are free to invoke P(n) at any point during the proof.

I edited my work in my previous post, can you quickly look it over and see if anything is still wrong?

The proof is OK, but you deleted the problem statement, i.e., the claim you are proving. In fact, I don't understand why you need an inductive definition of B_n. An inductive (or recursive) definition is usually needed when one does structural induction on that definition. You are doing induction on n, not on the definition of B_n. In any case, for n > 0 you either say

B_n = {2^0, ..., 2^(n-1)}

(no need to set apart B_1), or, if you want to avoid informal ...,

B_1 = {1}, B_n = B_n ∪ {2^(n-1)}.

Then you need to write the claim you are proving.

When you define P(n), you don't need ∀n. What you are proving is ∀n P(n), so P(n) is ∀t, 0 <= t < 2^n -> ...

so i should change my inductive definition to
∀n∈ℕ+ Bn={2^0}, if n=1; {2^0,2^1,…,2^(n-1)}, if n>1

(fragment of it) Proof:

Let P(n) be the predicate that ∀t∈ℕ, 0≤t<2^n → ∃ subset A s.t. A⊆B_n ˄ ∑[x∈A]x = t.

Claim: ∀n>0 P(n) holds.
(should I put a claim statement? If so can I write it like this, since P(n) is defined?)

Originally Posted by Sneaky

so i should change my inductive definition to
∀n∈ℕ+ Bn={2^0}, if n=1; {2^0,2^1,…,2^(n-1)}, if n>1

No,

Originally Posted by emakarov

you either say

B_n = {2^0, ..., 2^(n-1)}

(no need to set apart B_1), or, if you want to avoid informal ...,

B_1 = {1}, B_n = B_n ∪ {2^(n-1)}.

(fragment of it) Proof:

Let P(n) be the predicate that ∀t∈ℕ, 0≤t<2^n → ∃ subset A s.t. A⊆B_n ˄ ∑[x∈A]x = t.

Claim: ∀n>0 P(n) holds.
(should I put a claim statement? If so can I write it like this, since P(n) is defined?)

Usually they start by writing the original statement to prove ("For every n > 0 and 0 <= t < 2^n, ...") and define the induction statement P only inside the proof.

If I write the claim, then wouldn't defining P(n) after seem redundant? Can't I formally say the claim in the beginning and define P(n) after without writing the whole claim again for P(n)? Is there a way to combine both?

If I write the claim, then wouldn't defining P(n) after seem redundant?

Yes. The way I look at it, the question is given to you from a textbook, or by your boss, etc.; it's outside of your control. What you control is located after the word "Proof": there you define concepts that you need. That said, this is a question of style, not mathematics.

Can I write it like this:

Claim: ∀n∈ℕ>0, ∀t∈ℕ, 0≤t<2^n → ∃ subset A s.t. A⊆B_n ˄ ∑[x∈A]x = t.

Let P(n) be the predicate that ∀t, 0≤t<2^n → ∃ subset A s.t. A⊆B_n ˄ ∑[x∈A]x = t.