# My first attempt at proofs, from Understanding Analysis

• Feb 18th 2011, 11:17 PM
drgonzo
My first attempt at proofs, from Understanding Analysis
Hey all,

This is my first attempt at any sort of a proof in mathematics. I'm reading through the book 'understanding Analysis' by Abbott. Can you take a look and tell me what you think? Have I left out anything major as required by induction or contradiction?

Cheers.

**Chapter 1**

**Exercise 1.2.9. **
Show that the sequence (x1, x2, x3, . . . ) defined in Example 1.2.7 is bounded above by 2; that is, prove that Xn ≤ 2 for every n ∈ N.

**Example 1.2.7**

Let X1 = 1, and for each n ∈ N define
Xn+1 = (1/ 2)Xn + 1.

**Proof by Induction**

where n ∈ N
X1 = 1 <= 2

Xn+1 = (1/ 2)Xn + 1 <= 2

Xn/2 <= 1

Xn <= 2

where n ∈ N
Xn !<= 2

Xn > 2

Xn/2 > 1

Xn/2 + 1 > 2 = Xn+1

if n = 0

Xn+1 = 1 !> 2

Therefore Xn+1 <= 2

**Reasoning via analysis**

Let X1 = 1, and for each n ∈ N define

Xn+1 = (1/ 2)Xn + 1.

Thus Xn/2 is always (denominator -1) / denominator for all Xn

example n= 1 Xn/2 = ½. N = 2, Xn/2 = ¾, n = 3, Xn/2 = 7/8 etc...

Therefore (1/ 2)Xn + 1 is always something less then unity + unity which will always be less then 2.

**Exercise 1.2.10. **
Let y1 = 1, and for each n ∈ N define yn+1 = (3yn + 4)/4.

(a) Use induction to prove that the sequence satisfies yn < 4 for all n ∈ N.

**(a) Proof by induction**

y1 = 1 < 4, for each n ∈ N

yn < 4

3yn < 12

(3yn +4)/4 < 4 = yn+1

Therefore

yn = (4yn+1 -4 )/ 3 < 4

yn+1 < 4

or

yn < yn+1

yn < (3yn +4)/4

yn < 4

**Exercise 1.2.11**
If a set A contains n elements, prove that the number of
different subsets of A is equal to 2^n. (Keep in mind that the empty set ∅ is
considered to be a subset of every set.)

**Proof via induction**

for each n ∈ N

If n >=0, A>=1

A = 2^n

2^n >= 1

using log rules

n >= 0

n +1 >= 1

using logs

2^(n+1) > 2

Therefore

2^(n+1) = An+1

An+1 > An > A
• Feb 19th 2011, 01:14 AM
DrSteve
Here is an analysis of the first exercise you did. It's a good first attempt, but there are several errors:

I don't quite understand your first induction proof. The base case is correct. The inductive step should look like this:

Assuming that $x_n\leq 2$, we have $x_{n+1} = (1/ 2)x_n + 1 \leq (1/2)(2)+1=1+1=2$.

Mistake 1: A proof by contradiction would say "there is some $n\in \mathbb{N}$ such that $x_n>2$". You don't get to pick the $n$ for which this happens.

Mistake 2: You look at $n=0$, but $n=0$ is not even defined in this problem.

An actual proof by contradiction here would require using the well-ordering property of the integers to get a least counterexample. This is essentially the same as induction, but less elegant.

I'm not sure I understand your reasoning by analysis, but it seems like an informal argument, and not a mathematical proof.

The proof by induction is the best way to go here.

The second question looks almost correct. For a cleaner argument follow what I did above for the first exercise.

The last one is completely wrong. You seem to think that a set is a number. This is false. A set is a collection of objects. Here is a specific example:

$A=\{ elephant, banana \}$

The set A has 2 elements. The 4 subsets of $A$ are:

$\emptyset$, $\{ elephant \}$, $\{ banana \}$, $A$

A proof by induction for the last problem would involve taking one element of the set, let's call it $x$, and counting the subsets that exclude $x$, and the subsets that contain $x$, then adding these results together.
• Feb 19th 2011, 02:01 AM
drgonzo
Here is an analysis of the first exercise you did. It's a good first attempt, but there are several errors:

Quote:

Originally Posted by DrSteve
I don't quite understand your first induction proof. The base case is correct. The inductive step should look like this:

I originally wrote the proof out on paper. Then after writing out for the web i left out the part where I had proven xn. I then went backwards from xn+1 to xn. Sorry about that.

Also thank you for writing out an example, I will review it.

Quote:

Originally Posted by DrSteve

I'm not sure I understand your reasoning by analysis, but it seems like an informal argument, and not a mathematical proof.

This wasn't supposed to be a proof, It was just my own informal analysis on the pattern of the function. I probably should of left it out.

Quote:

Originally Posted by DrSteve
The last one is completely wrong. You seem to think that a set is a number. This is false. A set is a collection of objects. Here is a specific example:

I didn't actually think A was a number and not a set, i should of checked that question. I just assigned the same variable A to the equation 2^n that defines the number of subsets of A . Very stupid.

I'll redo it and post it again.

Thanks for taking the time out and writing a reply. I will go over your examples.
• Feb 19th 2011, 08:36 PM
drgonzo
Attempt #2

Exercise 1.2.9.
Show that the sequence (x1, x2, x3, . . . ) defined in Example 1.2.7 is bounded above by 2; that is, prove that Xn ≤ 2 for every n ∈ N.

Example 1.2.7

Let X1 = 1, and for each n ∈ N define
Xn+1 = (1/ 2)Xn + 1.

Proof induction

Basis:

for n =1, X1 = 1 < 2

Thus it holds for n = 1

Induction Steps:
if Xn < 2
Xn/2 < 1
Xn/2 + 1 < 2

Xn/2 + 1 = Xn+1
Xn+1 < 2

Since both Basis and Induction Steps are proved it holds that the sequence (x1,x2,x3..) is bounded by 2.
Q.E.D

Exercise 1.2.10.
Let y1 = 1, and for each n ∈ N define yn+1 = (3yn + 4)/4.
(a) Use induction to prove that the sequence satisfies yn < 4 for all n ∈ N.

Basis:
for n = 1, y1 = 1 < 4

Induction Steps:

If Yn < 4

3Yn < 12
(3Yn +4)/4 < 4

(3Yn +4)/4 = Yn+1

Yn+1 < 4

Since it holds for both Basis and Induction Steps the sequence ( y1,y2,y3...) is bounded by 4.
Q.E.D

b) Show that {y1,y2,y3...) is increasing by induction

Basis:

given n= 1,Y1 = 1

Induction steps:

If increasing, y1<y2<y3...

1<yn<yn+1

1<(3Yn-1+4)/4 < (3Yn +4)/4
1< 7/4 < 25/16

It shows that the induction steps and the Basis holds. Therefore the sequence { y1,y2,y3...} is increasing.
Q.E.D?

Exercise 1.2.11
If a set A contains n elements, prove that the number of
different subsets of A is equal to 2^n. (Keep in mind that the empty set ∅ is
considered to be a subset of every set.)

Basis:

Given Fn = 2^n is the function that defines the number of subsets of a given set with n elements.

n =0, Fn = 1.

Induction Steps:

Fn = 2^n
2Fn = 2^(n+1)

2^(n+1) = Fn+1

Fn+1 = 2Fn
Fn+1 = 2(2^n)
Fn+1 = 2^(n+1)

It shows that the induction steps and the Basis holds. Therefore the function Fn = 2^n which represents the number of subsets of a set with n elements holds for all n where n ∈ N.
Q.E.D?

• Feb 20th 2011, 01:06 AM
DrSteve
The first two are essentially correct. The inductive step could be written just a bit better however. When you're writing a proof you should write as if you're explaining to another person. Let me "fix up" your first argument as an example. Here is what you wrote:

if Xn < 2
Xn/2 < 1
Xn/2 + 1 < 2

Xn/2 + 1 = Xn+1
Xn+1 < 2

And here it is with some slight revisions:

if Xn < 2, then Xn/2 < 1 from which it follows that Xn/2 + 1 < 2. Since Xn/2 + 1 = Xn+1, we have Xn+1 < 2.

I'm not really sure that I understand your third argument.

Your last argument is missing important details. Let me do the base case for example:

If n=0, then $A=\emptyset$. So $A$ has exactly one subset, $\emptyset$.

In your inductive step you claim that $F_{n+1}=2F_n$. Why is this true?
• Feb 20th 2011, 05:34 PM
drgonzo
Quote:

Originally Posted by DrSteve
In your inductive step you claim that . Why is this true?

Because we are working with a base 2 system on the right hand side. Thus to add one to the exponent n of 2^n we need to times both sides by 2^1.
Thus 2^n(2) = 2^(n+1) which is 2Fn. which makes sense because exponents tell us that M^n = MxM ( n times) so 2Fn = 2x2(n+1 times).

I hope my explaination is clear.
• Feb 20th 2011, 06:02 PM
DrSteve
You never explained why $F_{n+1}=2F_n$.
• Feb 20th 2011, 06:43 PM
drgonzo
Quote:

Originally Posted by DrSteve
You never explained why $F_{n+1}=2F_n$.

How would I go about explaining that formally?
Do i have to explain the rules of exponents and logs being used? to show 2^n+1 = 2^n*2.

Do i need to add assumptions to to beginning of the proof? i.e that the rules of exponents are being used or something like that?

also it makes sense if you have set S, where |P(s)| = 2^n, n is the amount of elements in S.

then if you add one more element thus n+1 the amount of powersets becomes 2^n + 2^n which is the same as 2^n(2) = 2^(n+1)

because adding another element (I) to S the new set Q = S U (i)
for example S = ( 1) P(s) = { enpty, 1}
Q = ( 1, i), p(Q)= { empty, 1, i, (1,i)}
thus
|P(s)| = 2^n and |P(Q)| = 2^n + 2^n = 2(2^n)= 2^(n+1)

Is that what you mean?

Thanks

Dylan
• Feb 20th 2011, 07:30 PM
DrSteve
Let $A$ be a set with n+1 elements, and let $x$ be in $A$. Then the set $B=A\setminus \{x\}$ has n elements. By the inductive hypothesis $P(B)$ has $2^n$ elements. The map $C\rightarrow C\cup \{x\}$ is a bijection from $B$ to the subsets of $A$ containing $x$. Thus there are $2^n$ elements of $A$ that do not contain $x$, and $2^n$ elements of $A$ that contain $x$ for a total of $2^n+2^n=2(2^n)=2^{n+1}$ elements.
• Feb 20th 2011, 08:53 PM
drgonzo
wow, thats a really elegant way of doing it. Thank you. I think I should probably go over set theory some more before i attempt analysis then.
• Feb 20th 2011, 09:01 PM
DrSteve
To do analysis you just need a little bit of set theory. You should have a basic understanding of subsets, power sets, unions, intersections, cartesian products, equivalence relations, functions, using injections and bijections to compare cardinalities (sizes) of sets. This material is usually covered in the introductory sections of most analysis texts.