Results 1 to 8 of 8

Math Help - Proof using principle of strong induction

  1. #1
    Junior Member
    Joined
    Sep 2009
    Posts
    42

    Proof using principle of strong induction

    Let the numbers x_n be defined as follows: x_1≔1, x_2≔2, and x_(n+2)=(1/2)((x_(n+1))+(x_n)) for all n∈N. Use the Principle of Strong Induction to show that 1 ≤ x_n ≤ 2 for all n∈N.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    Here is a generic outline. It may seem obvious, but it is indispensable, and since you have not indicated where your difficulty lies, it is better to start there.

    1. Represent your problem as "for all n∈N, P(n)". Here P(n) is the induction statement, also called induction hypothesis in the case of regular (not strong) induction. Note that it depends on n and for each given n it is a proposition, i.e., it is either true or false. In particular, P(n) is not a number.

    2. Prove "for all n, P(0), ..., P(n - 1) imply P(n)". This is inductive step. For this, fix an arbitrary n and assume all of P(0), ..., P(n - 1). From here, try to prove P(n).

    Consider step 2 in more detail. Let's fix n. If n = 0, then the list P(0), ..., P(n - 1) is empty. This means that P(0) has to be proved from scratch, without any assumptions. When n = 1, you assume P(0) and use it to prove P(1). For n = 2, you assume P(0) and P(1) and prove P(2), etc.

    Hint: Here it is enough to have two induction statements P(n - 2) and P(n - 1) as the hypothesis in the inductive step. Note, however, that this does not work for all n. When n = 1, n - 2 is not a natural number. As noted above, to prove P(1) one can only rely on P(0). Thus, for this problem, inductive step can be formulated this way: Prove P(0), then prove P(1) assuming P(0), and for all n >= 2, prove P(n) assuming P(n - 2) and P(n - 1). This last part can be reformulated as follows: for all n >= 0, prove P(n + 2) assuming P(n) and P(n + 1).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2010
    Posts
    185
    Thanks
    13
    Can we restate the problem.

    If x_1:=1,\,x_2=2 then proove that for all n>2 is x_n=\frac{x_{n-1}+x_{n-2}}{2}\in [1,2].

    In case of n_0=3 the property is obviously true: x_3=\frac{2+1}{2}=\frac{3}{2}\in[1,2]..

    For arbitrary k>n_0 the stated property is true for all n such that n_0\leq n \leq k because

    x_{n}=\frac{\overbrace{\overbrace{x_{n-1}}^{\in [1,2]}+\overbrace{x_{n-2}}^{\in [1,2]}}^{\in[2,4]}}{2}\in[1,2].

    So it is true for the case k+1. Hence the statement is true for all n\in\mathbb{N}

    How does this seem?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    The math (inequalities about the arithmetic mean) behind this problem is pretty easy. However, the logic has to be expressed precisely.

    In case of n_0=3 the property is obviously true: x_3=\frac{2+1}{2}=\frac{3}{2}\in[1,2].
    There is no need to consider x_3 separately because it is covered by the inductive step.

    For arbitrary k>n_0 the stated property is true for all n such that n_0\leq n \leq k because
    This is not something to be proved. The fact that the induction statement is true for all precedent n is assumed in the inductive step.

    So it is true for the case k+1.
    It is not clear how this follows because your argument above does not mention k+1.
    Last edited by emakarov; September 20th 2010 at 05:30 AM. Reason: equalities |-> inequalities
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Sep 2010
    Posts
    185
    Thanks
    13
    I was trying my best to fit my logic according to this. My reasoning was that if you prove that the induction basis P(n_0) is true, and if you prove that for any k>n_0 the statement P(n) is true for all n_0\leq n \leq k then it follows that it is true for all n\in \mathbb{N}.

    Thus the statement is true up to "index" k which can be arbitrarily large natural number, so it has to be true for all natural numbers.

    If something is wrong with this reasoning please let me know exactly what is wrong so I will know better in the future.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    MathoMan, in both of your posts, something is not clear about the inductive step. Namely, I am not sure what the induction hypothesis and the goal are.

    In the link you gave, the inductive step for any number k proceeds as follows: Assume P(n) for all n0 <= n <= k (induction hypothesis) and prove P(k + 1) (goal). On the other hand, in your first post you seem to fix k and then prove (not assume) P(n) for all n0 <= n <= k. In doing that, it is not clear what hypothesis you rely on.

    In your second post, you again say that the person using induction is supposed to prove, for any given k, that P(n) holds for all n such that n_0\leq n \leq k. Of course, if one proves that, it trivially follows that P(k) is true for all k\in\mathbb{N}: since, for any k, P(n) holds for all n_0\leq n \leq k, in particular, P(k) holds. However, the main idea of induction is not to prove P(n) for all n0 <= n <= k, or even its special case P(k), in one step. One breaks the proof of P(k) into k steps and uses the results of the previous steps (proofs of P(0), ..., P(k - 1)) to show P(k).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Sep 2010
    Posts
    185
    Thanks
    13
    I appreciate your replies. So you say that I should assume that for n such that 2<=n<=k all numbers x_n are in[1,2]. Ok so induction step remains trivial to prove using the same logic used in my earlier post. By induction hypothesis both x_k and x_(k-1) are in[1,2] hence their arithmetic mean which is x_(k+1) also has to be in [1,2].

    Is that better?
    Sorry, I'm typing on my iPhone and that's why there's no TeX.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    Yes, that's fine.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proof by strong induction
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 27th 2011, 05:06 PM
  2. Replies: 1
    Last Post: November 16th 2010, 02:36 AM
  3. Proof Using Strong Induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 27th 2009, 07:30 AM
  4. Proof Using Strong Induction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 23rd 2009, 11:26 AM
  5. Strong Induction proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 5th 2008, 01:42 PM

Search Tags


/mathhelpforum @mathhelpforum