Mathematica Help with Proof and Mathematical Induction problem

[alancj]

Help with Proof and Mathematical Induction problem

Here is my problem I need to solve:
"Prove that the statement: \frac {1}{5} + \frac{1}{5^2} + \frac{1}{5^3} +... + \frac{1}{5^n} = \frac{1}{4}(1-\frac{1}{5^n}) is true for all positive integers n. Write your proof in the space below."

I don’t know where to start. The sub-chapter in my textbook that talks about it doesn’t make any sense. Here are the two pages relevant to this problem.

My first question is why is n redefined as k? It seems pointless. Why not just say “show the statement is true for the next integer n+1”?

Second question: When n=1 you just replace a 1 for all the spots where an n appears in the equation; so why on Earth when you make it n=k+1 don’t you just put in a 2 wherever an n is (or k) instead of actually inserting the whole k+1? It seems like they make it more complicated then it needs to be.

Third question: What the heck is with the x + x + x + … + x= part? I don’t understand what it is supposed to mean or how it is relevant to the problem given in the example (or in my problem I need to answer).

Fourth question: why, in example 1, do they add a (k+1)^2 to each side of the problem? Isn’t the whole point to just solve the equation with more than one integer to prove that it is true for all integers? I don’t get it!

Fifth question: I don’t understand the conclusion of example 1. They just say “This proves that… for all positive integers n.” How does it prove it? They didn’t even use real numbers? It is just a bunch of gibberish!

Thoroughly confused.

Maybe if I can understand the example that they give me I can have a fighting chance at answering this exam question (which I need to show my work for).

Thanks,
Alan

 

[0rthodontist]

Help with Proof and Mathematical Induction problem

Here is my problem I need to solve:
"Prove that the statement: \frac {1}{5} + \frac{1}{5^2} + \frac{1}{5^3} +... + \frac{1}{5^n} = \frac{1}{4}(1-\frac{1}{5^n})

since it's an exam problem I'm guessing you don't want hints directly about this problem

I don’t know where to start. The sub-chapter in my textbook that talks about it doesn’t make any sense. Here are the two pages relevant to this problem.

My first question is why is n redefined as k? It seems pointless. Why not just say “show the statement is true for the next integer n+1”?

They did something a little odd here. They are using "n" to mean the first number that the induction starts on, and simultaneously using it to mean any number that you are trying to prove the proposition for. It might have been clearer to use a different letter--say "m"--to indicate the starting number. With a proposition S(n), it would go like:
1. show that S(m) is true for a starting number m
2. show that where n >= m, if S(n) is true, then S(n + 1) is true.
3. Conclude that S(n) is true for any n >= m.

What they said is basically
1. show that S(n) is true for a starting number n
2. show that where k >= n, if S(k) is true, then S(k + 1) is true.
3. Conclude that S(n) is true for any n >= "n" where the "n" in quotes is the "starting number" as in 1., and the other n's are any number. This looks like a scope error to me.

So, I think they should not have used n to start their induction when they are denoting the general statement also using n. However, their using "k" is fine. All "k" is, is any number >= the number they start on. If they start on 3, then k might be 3, 9, or 502, for example, but it couldn't be 2. In their example here they start on 1, so k is any positive integer.

Second question: When n=1 you just replace a 1 for all the spots where an n appears in the equation; so why on Earth when you make it n=k+1 don’t you just put in a 2 wherever an n is (or k) instead of actually inserting the whole k+1? It seems like they make it more complicated then it needs to be.

If they showed that S(1) is true and then that S(2) is true, would that tell you anything about whether S(3) is true?

They have to show that for ANY integer greater than or equal to their starting integer, the statement is true. To do this they show that if the statement is true for any number, the statement is also true for the next number. In their ladder analogy, they show that for a rung on the ladder--any rung, whether it's the second or the fiftieth--that IF you can climb to that rung, THEN you can climb to the next rung. Since you can climb to the first rung, they conclude you can climb to any rung.

Third question: What the heck is with the x + x + x +… + part? I don’t understand what it is supposed to mean or how it is relevant to the problem given in the example (or in my problem I need to answer).

I don't know what you're referring to here.

Fourth question: why, in example 1, do they add a (k+1)^2 to each side of the problem? Isn’t the whole point to just solve the equation with more than one integer to prove that it is true for all integers? I don’t get it!

No--the point is to induct on the integers and show that if it's true for any integer then it's true for the next one. Just because a statement is true for two or three integers doesn't mean it has to be true for all integers.

Fifth question: I don’t understand the conclusion of example 1. They just say “This proves that… for all positive integers n.” How does it prove it? They didn’t even use real numbers? It is just a bunch of gibberish!

Thoroughly confused.

Maybe if I can understand the example that they give me I can have a fighting chance at answering this exam question (which I need to show my work for).

Thanks,
Alan

Try this:
Draw five or six dots horizontally, and circle the leftmost dot. Now consider this rule:
"If a dot is circled, then the dot immediately to its right also must be circled."
How can you change your drawing to make it agree with this statement?

 

[alancj]

I think every one of my questions was misunderstood. All the things I already understood were explained and yet none of my questions were answered.

It’s my fault… I wasn’t clear enough. Here are the basic questions I have.

What are they doing in example 1?

Starting at step 3 is where they start doing things for reasons that they don’t bother to give me.

First... I want to know why they add (k+1)^2 to each side.

Second… I want to know why they replace all the k’s with k+1’s. Why don’t they just use the number 2? If k \geq n and n=1 and you need to show that the statement is true for the next integer k+1 then logic would say that the next integer to try and solve for is 2. If both sides end up equal then you know that the statement is true for all integers \geq n. They replaced all the n’s in step one with a 1 and solved it like a normal problem, so why can’t they do the same in step 3 only using the value of k+1 (which is 2)?

And how can they conclude it is proven if it was never solved in the first place? In other words, there are no numbers to look at on the opposite side of an = sign (like in step 1) that you can use to see if they are equal; and then be able to conclude if the number you used to solve the problem was valid or not. Each side of the equation isn’t even the same.

Thanks,
-Alan

 

[0rthodontist]

To understand why they add (k + 1)^2 to each side, you have to understand induction in the first place. They can't just show that the statement is true when n = 1 or n = 2--they have to show it's true for every possible n. As I mentioned, k is not 1 or 2--k can be ANY integer greater than their starting value of 1. k could be 1000. What you want to do with k is say (still using S(n) to denote the statement),
"For ANY number k greater or equal to the starting value, (S(k) is true) implies (S(k + 1) is true)"

So what they start with is 1^2 + 2^2 + 3^2 + ... + k^2 = k(k+1)(2k+1)/6. This equality is the statement S(k). Now they want to show that, given S(k), S(k+1) must be true. What is S(k+1)?
S(k+1) = "1^2 + 2^2 + 3^2 + ... + k^2 + (k+1)^2 = (k+1)((k+1)+1)(2(k+1)+1)/6"
They add (k+1)^2 to both sides of the equation S(k) so that the left side of the equation will be equal to the left side of S(k+1). Then they try to show that after adding (k+1)^2, the right side of the equation is also like the right side of S(k+1), which is just algebra. This demonstrates that S(k) implies S(k+1). You Assume S(k) is true, and reasoning from there you reach the conclusion S(k+1) is true, therefore whenever S(k) is true, S(k+1) must also be true.

Here is a statement (a false one): "The sum of the first n positive integers is 2n - 1" Using your method, you subsitute in for n = 1:
1 = 2(1) - 1 = 1, so S(1) is true
Then since you want to substitute in n = 2 here, you get:
1 + 2 = 2(2) - 1 = 3, so S(2) is true
But S(3) is not true since 1 + 2 + 3 = 6 which is not equal to 2(3) - 1 = 5. So S(n) is not true in general--just showing that S(1) and S(2) are true isn't enough to show S(n) is true.

If you're still having trouble, try the thing with the dots and circles I said earlier.

 

[Integral]

alancj,
your questions indicate that you do not understand the induction process. Please read, very carefully every word of Ortho's post IMHO he answered all of your questions except 3 which makes no sense to me either. Let me try.

Question 1:
This in the heart of the induction process, you make the assumption that your relationship is true for some UNSPECIFIED integer, you can call it what ever you want, k works as good as anything else. What you cannot do is assign it any specific value.

Question 2:
You would have us prove it for each integer?
The first step is to prove the relationship is true for some specific integer, 1 is usually picked because it is easy. You could do it for n=10000 if you wanted. The idea is to show that it works for a specific integer.

Question 3:
Makes no sense.

Question 4:
This is the induction step, this is where the work begins. They have chosen a different way of doing it then I am accustomed to, but, it works. The LHS is exactly what we need. In this case the sum of integers squared up to k+1. They have added (k+1)² to the left hand side to maintain equality. Now you need to show that the RHS is equivalent to the original relationship. How do you get there from here? You know where you want to go and you just have to play with it to get what you want. Of course algebraic errors will kill you. Persistence is a very useful trait when doing this type of problem.

Question 5:
If you replace every occurance of k+1 in their final expression with n you are back to your starting place. Once again, you cannot use a specific value as that only proves the relationship for THAT integer, we need to prove it for ALL integers. That is why we assume it for some unspecified, but named, integer. This is a critical concept to get a grasp on. You will find, that in general mathematicians do not work with specific numbers, that is accounting, or arithmetic, not mathematics.

Ortho'
If I could spell your full name you would have your HH ribbon by now. Be warned that it may show up soon.

 

[alancj]

In question three I was talking about the part of the problem(s) where there is a bunch of numbers being added together and then it has the … part and then the rest of the evil problem follows. So in example 1 in my textbook I’m talking about this part: 1^2 + 2^2 + 3^2 +…+n^2= so, everything before this thing …

So the question is... What is it there for?

-Alan

 

[Integral]

I am very cursious as to just what you think the point of the example is? What are they trying to prove?

 

[alancj]

I am very cursious as to just what you think the point of the example is? What are they trying to prove?

They are trying to prove that the statement is true for any integer greater then or equal to the starting value of 1.

 

[d_leet]

They are trying to prove that the statement is true for any integer greater then or equal to the starting value of 1.

I think integral meant what statement do you think they're trying to prove.

 

[alancj]

I think integral meant what statement do you think they're trying to prove.

What kind of question is that? It says right at the beginning of the example. It's not like I can't read.

I'm working on replying to the other stuff...

 

[d_leet]

What kind of question is that? It says right at the beginning of the example. It's not like I can't read.

I never said you couldn't read, but I agree with Integral and Orthodontist that your questions indicate that you don't understand the concepts behind induction, because if you truly understood induction you wouldn't have asked what the 1²+2²+3²+...+n² stuff was for.

 

[0rthodontist]

Something that you might not be seeing is that 1² + 2² + ... + n² is "the sum of the squares of the first n positive integers."

 

[Integral]

They are trying to prove that the statement is true for any integer greater then or equal to the starting value of 1.

This is not a very complete answer.

What is "the statement" that the example proves?

 

[HallsofIvy]

Going back to "My first question is why is n redefined as k? It seems pointless. Why not just say “show the statement is true for the next integer n+1”? ", many people do just use n and n+1 but I strongly recommend using a different letter such as k. The reason is that many people confuse, say, "7ⁿ-1 is divisible by 6 for some n" with "7ⁿ-1 is divisible by 6 for all n" which is what you are trying to prove. While it is perfectly proper to use n and n+1, I think that by using a different letter, k, you are making it clearer that you are not assuming the origina statement but only that it is true for some specific number (which you have already proved in step 1).

 

[HallsofIvy]

In question three I was talking about the part of the problem(s) where there is a bunch of numbers being added together and then it has the … part and then the rest of the evil problem follows. So in example 1 in my textbook I’m talking about this part: 1^2 + 2^2 + 3^2 +…+n^2= so, everything before this thing …

So the question is... What is it there for?

-Alan

Since, after several requests, you still haven't answer "what is the statement you are trying to prove", the statement, and as you say "It says right at the beginning of the example", that
1+ 2^2+ 2^2+ \cdot\cdot\cdot + n^2= \frac{n(n+1)(2n+1)}{6}

That's exactly why 1^2 + 2^2 + 3^2 +…+n^2= is there- it is part of what you are trying to prove.

If n= 1, then 1^2= 1 is that the same as
\frac{1(1+1)(2(1)+1)}{6}?

Now suppose
1+ 2^2+ 2^2+ \cdot\cdot\cdot + k^2= \frac{k(k+1)(2k+1)}{6}
for some number k (and it's alright with me if you want to retain the n; just remember that saying "for some n" is not the same as saying "for all n"), what do you get for
1+ 2^2+ 2^2+ \cdot\cdot\cdot + n^2+ (n+1)^2?