Induction confusion
Hi guys,
I'm having a look at mathematical induction, with relevance to the 2nd question on this link - http://home.cc.umanitoba.ca/~thomas/Courses/InductionExamples-Solutions.pdf
Use the Principle of Mathematical Induction to verify that, for n any positive integer,6n-1is divisible by 5.
6k+1-1 = 6*6k - 1
this line makes sense but on the next line -1 and +6 just make arbitrary appearances, where does the -1 and + 6 come from?
I'm having a look at mathematical induction, with relevance to the 2nd question on this link - http://home.cc.umanitoba.ca/~thomas/Courses/InductionExamples-Solutions.pdf
Use the Principle of Mathematical Induction to verify that, for n any positive integer,6n-1is divisible by 5.
6k+1-1 = 6*6k - 1
this line makes sense but on the next line -1 and +6 just make arbitrary appearances, where does the -1 and + 6 come from?
Last edited on
6n-1
n = 2
12-1 = 11
11/5 not evenly divided.
?? not true.
I suspect you did not put () in the right places on your equations. The second one, k is not defined and the equation is nonsense as written.
I can't click the link but something is not right here.
n = 2
12-1 = 11
11/5 not evenly divided.
?? not true.
I suspect you did not put () in the right places on your equations. The second one, k is not defined and the equation is nonsense as written.
I can't click the link but something is not right here.
Last edited on
So you understand:
but are confused by the next line
The point of putting the
Simplifying to
6^(k+1) - 1 = 6 * (6^k) - 1 |
but are confused by the next line
= 6 * (6^k - 1) - 1 + 6 |
The point of putting the
- 1 inside the parens is to create the original pattern (6^k - 1). Because we put the - 1 inside the parens and the parens are multiplied by 6, we need to add 6 outside to keep the expression equal.Simplifying to
6*(6^k - 1) + 5 shows that the assumption holds since we have supposed "6^k - 1 is divisible by 5" to be true, and multiplying that by 6 still leaves it divisible by 5, and adding 5 also leaves it still divisible by 5.
@Jonnin made a couple of typos, what Dutch said is what I meant.
@Dutch that makes sense because 6(6^k - 1) = (6^k+1)- 6. but to get it back to the original value we have to add 6 and subtract -1 and that will bring us back to (6^k+1)-1
My induction skills suck, how do you notice these patterns? and how do you come up with conclusion to put the -1 inside the parens and also the -1 + 6 outside.
@Dutch that makes sense because 6(6^k - 1) = (6^k+1)- 6. but to get it back to the original value we have to add 6 and subtract -1 and that will bring us back to (6^k+1)-1
My induction skills suck, how do you notice these patterns? and how do you come up with conclusion to put the -1 inside the parens and also the -1 + 6 outside.
Last edited on
We are trying to prove that "6^k - 1 is divisible by 5". The magic of induction (similar to that of recursion) is that we only need to prove the base case(s) directly, and then we prove that "if it holds for k, then it holds for k + 1", which means we are allowed to assume the kth case in proving the k+1th case. So at some point we will use the pattern of the kth case in proving the k+1th case. In general you just stick in k+1 for k, then manipulate the thing so that part of it looks like the kth case again.
At that point you might just simplify both sides of the equation and show that they are equal and therefore that the equation is true, or you might show that whatever extra stuff is done to the kth case doesn't change what we are trying to prove like we did in this case.
You might want to read the wikipedia article:
https://en.wikipedia.org/wiki/Mathematical_induction
And perhaps google some other stuff:
https://www.google.com/search?q=mathematical+induction
At that point you might just simplify both sides of the equation and show that they are equal and therefore that the equation is true, or you might show that whatever extra stuff is done to the kth case doesn't change what we are trying to prove like we did in this case.
You might want to read the wikipedia article:
https://en.wikipedia.org/wiki/Mathematical_induction
And perhaps google some other stuff:
https://www.google.com/search?q=mathematical+induction
| So at some point we will use the pattern of the kth case in proving the k+1th case. In general you just stick in k+1 for k, then manipulate the thing so that part of it looks like the kth case again.] |
That makes sense, so the pattern of k appears in k+1 6( (6^k) -1)+6-1 .
I think (hopefully) eventually I'll be able to see these patterns for myself,
thanks Dutch
Last edited on
@adam2016
It's good to know how induction works ... but sometimes it's a rather round-the-houses way of proving anything.
Take the polynomial xk-1
xk-1=(x-1)*(xk-1+xk-2+...+x+1)
So, putting x=6,
6k-1=5*(whole-number factor)
So 6k-1 has a factor of 5.
The same method would then prove that
Ak-1
was always divisible by A-1 for any positive integers A and k.
It's good to know how induction works ... but sometimes it's a rather round-the-houses way of proving anything.
Take the polynomial xk-1
xk-1=(x-1)*(xk-1+xk-2+...+x+1)
So, putting x=6,
6k-1=5*(whole-number factor)
So 6k-1 has a factor of 5.
The same method would then prove that
Ak-1
was always divisible by A-1 for any positive integers A and k.
Last edited on
That's true, never thought of it like that.
Some proof by induction questions seem trivial such as the first question in the link I posted or a question asking for proof that a series of numbers n >= 1, 1+2 + 3 + n = (n (n+1))/2 but then some questions like the second one in the link and the one in question seem to trip me up.
Some proof by induction questions seem trivial such as the first question in the link I posted or a question asking for proof that a series of numbers n >= 1, 1+2 + 3 + n = (n (n+1))/2 but then some questions like the second one in the link and the one in question seem to trip me up.
the point of them is to trip you up, make you figure it out. At least at first, later the point is to show that the work you did is correct if you go into advanced math.
Another non-inductive way:
1. For any integer k greater than 0 the last digit of 6^k is 6.
2. For any integer to be divisible by 5 its last digit is 0 or 5.
3. From 1. the last digit of 6^k - 1 is 5.
4. QED
1. For any integer k greater than 0 the last digit of 6^k is 6.
2. For any integer to be divisible by 5 its last digit is 0 or 5.
3. From 1. the last digit of 6^k - 1 is 5.
4. QED
Topic archived. No new replies allowed.