Results 1 to 6 of 6
Like Tree1Thanks
  • 1 Post By HallsofIvy

Math Help - Induction, one prob. two proofs.

  1. #1
    Junior Member
    Joined
    Jul 2014
    From
    Ca, USA
    Posts
    47
    Thanks
    4

    Induction, one prob. two proofs.

    Prove that 1 + 4 + 7 … (3n-2) = (n)(3n-1) for all values of n e N.

    This statement can also be written:

    1) $\sum\limits_{n = 1}^k {(3n - 2)} = \frac{n}{2}(3n - 1)$

    The formulaic response to proving the case for N is to write:

    2) For n = k = 1, establish that both sides of 1) are equal.

    a) 3k-2 = 3(1) – 2 = 1
    b) (k/2)(3k-1) = (3(1)-1 = 1
    c) Case proved for n = 1.

    3) For n = k, assume that $\sum\limits_{n = 1}^k {(3k - 2)} = \frac{k}{2}(3k - 1)$ holds.

    4) For k + 1, show that $\sum\limits_{n = 1}^{k + 1} {(3k - 2)} = \frac{{(k + 1)}}{2}(3(k + 1) - 1)$ holds.

    5) $\sum\limits_{n = 1}^{k + 1} {(3k - 2)} = \left( {\sum\limits_{n = 1}^k {(3k - 2)} } \right) + (3k - 2)$ , substitution from 3) yields:

    6) $\sum\limits_{n = 1}^{k + 1} {(3k - 2)} = \left( {\frac{k}{2}(3k - 1)} \right) + (3k - 2)$ , several steps of basic algebraic manipulation yield:

    7) $\sum\limits_{n = 1}^{k + 1} {(3k - 2)} = \frac{{(k + 1)}}{2}(3(k + 1) - 1)$ thus it has been shown that by assuming statement 3) one can derive statement 4) thus demonstrating that equation 1) holds for k+1

    8) Since 1) holds for n = k = 1 and holds for k+ 1 whenever it holds for k, then it holds for all n of N by P.M.I.
    --------------------------
    Now I would like to take a different approach.

    Recursion Theorem: Given a set X, a e X, and a function F:X-->X , there exists a unique function G:N-->X such that G(1) = a, and G(s(n)) = F(G(n)) for all n e N.

    Prove the following statement is true for all N.
    1) $\sum\limits_{n = 1}^k {(3n - 2)} = \frac{n}{2}(3n - 1)$

    2) Let $L(k) = \sum\limits_{n = 1}^k {(3n - 2)} $

    3) Let $R(k) = \frac{k}{2}(3k - 1)$

    4) Showing that L(k) is well defined:

    a) Let k = 1, then L(1) = (3(1)-2) = 1, L(k) is defined for k = 1.
    b) Let F:N-->N, F(x) = x + (3n-2)
    c) Then, since $L(k + 1) = F\left( {\sum\limits_{n = 1}^k {(3n - 2)} } \right) = \sum\limits_{n = 1}^{k + 1} {(3n - 2)} $ it is established (by the Recursion theorem) that L(k) is well defined over N1.

    5) Showing that R(k) is well defined:

    a) Let k = 1, then (1/2) (3(1)-1) = 1, R(k) is defined for k = 1
    b) Let F:N-->N, F(x) = x + (3n-2)
    c) Then since $R(k + 1) = F\left( {\frac{k}{2}(3k - 1)} \right) = \left( {\frac{k}{2}(3k - 1)} \right) + (3k - 2) = \left( {\frac{{(k + 1)}}{2}(3(k + 1) - 1)} \right)$
    it is established (by the Recursion theorem)that L(k) is well defined over N1

    6) Finally, since the same function F was used to produce the “successoring” functions of L(k) and R(k) they must both (by the Recursion theorem) be generating the same set of images over N and hence each is not only well defined but equal to one another, therefore proposition 1) is proved to hold for all N1​.

    My brain is still ping ponging over whether this is right. Certainly any g can be composed within a specific F but only the right g will allow F to identically reproduce it’s input sequence of images from g albeit offset by one unit increment.

    So, the fact that, independently, F produces the unique successoring function for L AND R, and although both L and R appear very different from one another as do their respective successoring functions, both L and R produce the same set of pairs over N and are hence equal to one another, i.e identities of each other …. I think … my brain is still balking over this unlikely route of testing identities.

    Also, I am not sure that I have all of the notation right.

    Comments, corrections, clarifications most welcome. Thank you.
    Last edited by Ray1234; August 26th 2014 at 01:58 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,693
    Thanks
    1466

    Re: Induction, one prob. two proofs.

    Quote Originally Posted by Ray1234 View Post
    Prove that 1 + 4 + 7 … (3n-2) = (n)(3n-1) for all values of n e N.

    This statement can also be written:

    1) $\sum\limits_{n = 1}^k {(3n - 2)} = \frac{n}{2}(3n - 1)$
    Actually, this is incorrectly written- you have the "k" and "n" reversed on the left. It should be:
    \sum_{k= 1}^n 3k- 2= \frac{n}{3n- 1}.
    or [tex] \sum_{n= k}^n 3k- 2= \frac{k}{3k- 1}.


    The formulaic response to proving the case for N is to write:

    2) For n = k = 1, establish that both sides of 1) are equal.

    a) 3k-2 = 3(1) – 2 = 1
    b) (k/2)(3k-1) = (3(1)-1 = 1
    c) Case proved for n = 1.

    3) For n = k, assume that $\sum\limits_{n = 1}^k {(3k - 2)} = \frac{k}{2}(3k - 1)$ holds.
    This is confusing. You are using "k" to mean two different things.

    4) For k + 1, show that $\sum\limits_{n = 1}^{k + 1} {(3k - 2)} = \frac{{(k + 1)}}{2}(3(k + 1) - 1)$ holds.

    5) $\sum\limits_{n = 1}^{k + 1} {(3k - 2)} = \left( {\sum\limits_{n = 1}^k {(3k - 2)} } \right) + (3k - 2)$ , substitution from 3) yields:

    6) $\sum\limits_{n = 1}^{k + 1} {(3k - 2)} = \left( {\frac{k}{2}(3k - 1)} \right) + (3k - 2)$ , several steps of basic algebraic manipulation yield:

    7) $\sum\limits_{n = 1}^{k + 1} {(3k - 2)} = \frac{{(k + 1)}}{2}(3(k + 1) - 1)$ thus it has been shown that by assuming statement 3) one can derive statement 4) thus demonstrating that equation 1) holds for k+1

    8) Since 1) holds for n = k = 1 and holds for k+ 1 whenever it holds for k, then it holds for all n of N by P.M.I.
    --------------------------
    P.M.I? I would call this "proof by induction" but what does the "M" stand for?

    Now I would like to take a different approach.

    Recursion Theorem: Given a set X, a e X, and a function F:X-->X , there exists a unique function G:N-->X such that G(1) = a, and G(s(n)) = F(G(n)) for all n e N.

    Prove the following statement is true for all N.
    1) $\sum\limits_{n = 1}^k {(3n - 2)} = \frac{n}{2}(3n - 1)$
    again, this should be \sum_{k= 1}^n 3k- 2= \frac{n}{3n-1}

    2) Let $L(k) = \sum\limits_{n = 1}^k {(3n - 2)} $

    3) Let $R(k) = \frac{k}{2}(3k - 1)$

    4) Showing that L(k) is well defined:

    a) Let k = 1, then L(1) = (3(1)-2) = 1, L(k) is defined for k = 1.
    b) Let F:N-->N, F(x) = x + (3n-2)
    c) Then, since $L(k + 1) = F\left( {\sum\limits_{n = 1}^k {(3n - 2)} } \right) = \sum\limits_{n = 1}^{k + 1} {(3n - 2)} $ it is established (by the Recursion theorem) that L(k) is well defined over N1.

    5) Showing that R(k) is well defined:

    a) Let k = 1, then (1/2) (3(1)-1) = 1, R(k) is defined for k = 1
    b) Let F:N-->N, F(x) = x + (3n-2)
    c) Then since $R(k + 1) = F\left( {\frac{k}{2}(3k - 1)} \right) = \left( {\frac{k}{2}(3k - 1)} \right) + (3k - 2) = \left( {\frac{{(k + 1)}}{2}(3(k + 1) - 1)} \right)$
    it is established (by the Recursion theorem)that L(k) is well defined over N1

    6) Finally, since the same function F was used to produce the “successoring” functions of L(k) and R(k) they must both (by the Recursion theorem) be generating the same set of images over N and hence each is not only well defined but equal to one another, therefore proposition 1) is proved to hold for all N1​.

    My brain is still ping ponging over whether this is right. Certainly any g can be composed within a specific F but only the right g will allow F to identically reproduce it’s input sequence of images from g albeit offset by one unit increment.

    So, the fact that, independently, F produces the unique successoring function for L AND R, and although both L and R appear very different from one another as do their respective successoring functions, both L and R produce the same set of pairs over N and are hence equal to one another, i.e identities of each other …. I think … my brain is still balking over this unlikely route of testing identities.

    Also, I am not sure that I have all of the notation right.

    Comments, corrections, clarifications most welcome. Thank you.[/QUOTE]
    Thanks from Ray1234
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2014
    From
    Ca, USA
    Posts
    47
    Thanks
    4

    Re: Induction, one prob. two proofs.

    Yes, thank you for the correction of my notation. I had fiddled around with it for a while and was never really satisfied. I assume then that I am understanding the role of the Recursive theorem.

    P.M.I are initials for the "Principle of Mathematical Induction" as it is called in my text.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,391
    Thanks
    757

    Re: Induction, one prob. two proofs.

    You've got some of the letters mixed up. What you WANT to prove is this:

    $\displaystyle \sum_{k=1}^n (3k - 2) = \dfrac{n}{2}(3n - 1)$ <--note the position of $k$ as the "dummy index" and $n$ as the "number of terms".

    The function $L$ you want to define recursively, is:

    $\displaystyle L(n) = \sum_{k=1}^n (3k - 2)$

    and the $F:\Bbb N \to \Bbb N$ you want to use is:

    $F(m) = m + 3n + 1$, with $a = 1$.

    We need to SHOW (in order to apply the recursion theorem):

    $L(n+1) = F(L(n))$.

    Now:

    $\displaystyle L(n+1) = \sum_{k=1}^{n+1} 3k-2 = \sum_{k=1}^n 3k-2 + 3(n+1) - 2 = L(n) + 3n + 1 = F(L(n))$, as required. So $L$ is the unique function that satisfies this.

    Now if we define $R(n) = \dfrac{n}{2}(3n - 1)$ we need to show that $R$, too, satisfies these requirements.

    Now $R(1) = \dfrac{1}{2}(3-1) = 1 = a$, so we're good there (this corresponds to the "base case").

    Next, we need to verify that:

    $R(n+1) = F(R(n))$.

    Now $R(n+1) = \dfrac{n+1}{2}(3(n+1) - 1) = \dfrac{n+1}{2}(3n + 2) = \dfrac{n}{2}(3n + 2) + \dfrac{3n + 2}{2} = \dfrac{n}{2}(3n - 1) + \dfrac{3n}{2} + \dfrac{3n+2}{2} = \dfrac{n}{2}(3n - 1) + \dfrac{6n + 2}{2}$

    $= \dfrac{n}{2}(3n - 1) + 3n + 1 = R(n) + 3n + 1 = F(R(n))$, as required (this corresponds to the "inductive step").

    Hence, by UNIQUENESS, $L = R$.

    EDIT: there is still something "unsatisfactory" about this: the variable we are concerned with, is $n$. But in the formula for $F,\ n$ is a constant. So what we get here is a proof SCHEMA: one for every value of $n$.

    What we have is:

    $L(n+1) = L(n) + 3n + 1$ which is recursive since $L$ is on both sides. The trouble is that the expression "$3n+1$" depends on $n$. Watch what happens when we try to use $L((n+1)') = L(n+2)$:

    $L(n+2) = L(n+1) + 3(n+1) + 1 = F(L(n+1)) + 3n + 4 \neq F(L(n+1)) + 3n+1$, since $1 \neq 4$. So our "$F$" only works for that one $n$, and we want to prove it holds for EVERY $n$. I think there must be a way to "fix this", but I can't quite put my finger on it, at the moment. My feeling is we need to use a different $L$ and $F$.
    Last edited by Deveno; August 27th 2014 at 04:16 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jul 2014
    From
    Ca, USA
    Posts
    47
    Thanks
    4

    Re: Induction, one prob. two proofs.

    OK, thanks. I felt my formulation dubious from the beginning: Let F:N-->N, F(x) = x + (3n-2).

    Your clarification is helpful, I see what you are saying about a fixed n and a schema.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Jul 2014
    From
    Ca, USA
    Posts
    47
    Thanks
    4

    Re: Induction, one prob. two proofs.

    I am not sure that, for my purposes it is necessary to pursue an exact solution. What I think I have learned is that proving a proposition over N, as in the first half of my original post is much different then trying to show that a function is well defined.

    In showing a function is well defined one needs to create take some function like R(n) = (n/2)(3n-1), apply the argument (n+1) to get R(n) = ((n + 1)/2)(3(n+1)-1). Next one must simplify the right side in some fashion to revel how it might be "decomposed" by finding a suitable function F within which to nest R(n) to produce R(n+1).

    It appears to me now that finding the right F, i.e. decomposing R(n+1) is not a matter of procedure but a matter of, depending on the complexity of the expression, experience, cleverness, and fiddling around until you find something that works.

    Proving a proposition on the other hand might require equal cleverness but in more cases seems like it might be less difficult and does not require decomposing an expression.

    If I have this right I think I have learned what I wanted to know. Right now I am looking at different types statements that can be proved using the PMI.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Induction Proofs
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 6th 2012, 04:03 PM
  2. 2 proofs for unitary matrix/transformation prob.
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: February 18th 2011, 02:20 AM
  3. Proofs by Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 30th 2010, 10:11 AM
  4. Induction proofs
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 14th 2009, 08:32 PM
  5. proofs by induction
    Posted in the Algebra Forum
    Replies: 7
    Last Post: September 25th 2007, 04:14 AM

Search Tags


/mathhelpforum @mathhelpforum