Results 1 to 11 of 11

Math Help - My first attempt at proofs, from Understanding Analysis

  1. #1
    Newbie
    Joined
    Feb 2011
    Posts
    12

    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


    **Proof by Contradiction**

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    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.


    Your first proof by contradiction looks incorrect.

    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.
    Last edited by DrSteve; February 19th 2011 at 12:37 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2011
    Posts
    12
    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 View Post
    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 View Post


    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 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Feb 2011
    Posts
    12
    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?





    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Feb 2011
    Posts
    12
    Quote Originally Posted by DrSteve View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    You never explained why F_{n+1}=2F_n.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Feb 2011
    Posts
    12
    Quote Originally Posted by DrSteve View Post
    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
    Last edited by drgonzo; February 20th 2011 at 05:57 PM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Feb 2011
    Posts
    12
    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.
    Last edited by drgonzo; February 21st 2011 at 01:13 AM.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Need some help understanding some Analysis
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: January 15th 2012, 02:08 PM
  2. Complex Analysis - CR equation understanding
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: August 9th 2011, 12:09 AM
  3. Something I am having trouble understanding - complex analysis
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: April 26th 2010, 09:06 PM
  4. Analysis Absolute Value Proofs
    Posted in the Differential Geometry Forum
    Replies: 5
    Last Post: October 18th 2009, 08:05 AM
  5. more proofs in analysis
    Posted in the Calculus Forum
    Replies: 28
    Last Post: February 25th 2007, 02:42 PM

Search Tags


/mathhelpforum @mathhelpforum