# Thread: Induction, one prob. two proofs.

1. ## 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.

2. ## Re: Induction, one prob. two proofs.

Originally Posted by Ray1234
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]

3. ## 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.

4. ## 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$.

5. ## 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.

6. ## 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.