Basic Induct Q (1 Viewer)
- Thread starter Estel
- Start date
hatty
Banned
how so CM_Tutor?
Let n = 2k, where k is a positive integer:
Then n<sup>3</sup> + 2n = (2k)<sup>3</sup> + 2(2k) = 8k<sup>3</sup> + 4k = 4k(2k<sup>2</sup> + 1), which is obviously divisible by 4.
We now need only prove that k(2k<sup>2</sup> + 1) is divisible by 3: k(2k<sup>2</sup> + 1) = k(2k<sup>2</sup> - 2 + 3) = 2k(k + 1)(k - 1) + 3k
Both of these terms are divisible by 3. So, for even n, n<sup>3</sup> + 2n is divisible by both 4 & 3, and thus is divisible by 12.
Note - the above proof does not require k to be positive, and so it proves the result for all even n, including the negative cases.
Estel: if you need to prove the result for all even n, and wish to use induction, prove the result for all positive even n, and then take n = -k, where k is a positive even integer. It then follows that:
n<sup>3</sup> + 2n = (-k)<sup>3</sup> + 2(-k) = -k<sup>3</sup> - 2k = -(k<sup>3</sup> + 2k), which is divisible by 12 from the induction proof.
This completes the proof for positve and negative even integers.
Estel: if you need to prove the result for all even n, and wish to use induction, prove the result for all positive even n, and then take n = -k, where k is a positive even integer. It then follows that:
n<sup>3</sup> + 2n = (-k)<sup>3</sup> + 2(-k) = -k<sup>3</sup> - 2k = -(k<sup>3</sup> + 2k), which is divisible by 12 from the induction proof.
This completes the proof for positve and negative even integers.
Can somebody double check I've done this right?
A
When n=2
n^3+2n=12
Which is divisible by 12
B
Suppose that k is a positive even integer for which the statement is true.
That is, suppose
k^3+2k=12m, where m is some integer
We prove the statement for n=k+2
That is, we prove
(k+2)^3+2(k+2) is divisible by 12
(k+2)^3+2(k+2)
=k^3+6k^2+14k+12
=12m+6k^2+12k+12, by the induction hypothesis
=12(m+k^2/2 +k+1), which is divisible by 12 as required (k is an even integer, therefore k^2>=4 and is even, and therefore k^2/2 is an integer)
C
From parts A and B by mathematical induction the statement is true for all positive even integers n.
Suppose n is a negative even number,
then n=-k
n^3 + 2n
=(-k)^3 + 2(-k)
=-k^3 - 2k
=-(k^3 + 2k), which is divisible by 12, as proven by induction above.
Therefore, n^3+2n is divisble by 12 for all even integers n.
A
When n=2
n^3+2n=12
Which is divisible by 12
B
Suppose that k is a positive even integer for which the statement is true.
That is, suppose
k^3+2k=12m, where m is some integer
We prove the statement for n=k+2
That is, we prove
(k+2)^3+2(k+2) is divisible by 12
(k+2)^3+2(k+2)
=k^3+6k^2+14k+12
=12m+6k^2+12k+12, by the induction hypothesis
=12(m+k^2/2 +k+1), which is divisible by 12 as required (k is an even integer, therefore k^2>=4 and is even, and therefore k^2/2 is an integer)
C
From parts A and B by mathematical induction the statement is true for all positive even integers n.
Suppose n is a negative even number,
then n=-k
n^3 + 2n
=(-k)^3 + 2(-k)
=-k^3 - 2k
=-(k^3 + 2k), which is divisible by 12, as proven by induction above.
Therefore, n^3+2n is divisble by 12 for all even integers n.
Seems fine to me, but in the last bit, I'd add after "then n = -k" the statement, "where k is a positive even integer". This is needed for you to use the induction above.
Note: this is a minor, fairly nit-picky point.
Note: this is a minor, fairly nit-picky point.
One last question (sorry): if the question asks for you to prove it for n>=11 for example, without referring to n being an integer, do you just take it as a given? Or would you have n=k+x or something like that? And is 0 even?... well that's really 3 questions.
Very big thankyou.
Very big thankyou.
Last edited:
You can usually take n to be an integer, as it is usually implied in the question. Eg.
Show, using mathematical induction, that 1 + 2 + 3 + ... + n = n(n + 1) / 2, for n > 0.
This doesn't specifically say that n must be an integer, but it's implied by the fact that 'n' is given as the general term of a series with specific terms '1', '2', and '3'. Under these circumstances, n must be an integer.
Similarly, in the above question, 'even n' requires n to be an integer - after all, how can a non-integer be even?
Show, using mathematical induction, that 1 + 2 + 3 + ... + n = n(n + 1) / 2, for n > 0.
This doesn't specifically say that n must be an integer, but it's implied by the fact that 'n' is given as the general term of a series with specific terms '1', '2', and '3'. Under these circumstances, n must be an integer.
Similarly, in the above question, 'even n' requires n to be an integer - after all, how can a non-integer be even?
You're right, being an integer is not implied by 2<sup>n</sup> > 3n<sup>2</sup> for n > 2 (actually, this statement isn't true for integers until n > 7). However, induction works on the integers. To prove such a result, for all values n => 8, for example, is extremely complicated by induction. (It could be done by an Extn 2 student, using strong induction.) This would be much easier done by defining a function f(n) = 2<sup>n</sup> - 3n<sup>2</sup>, and showing that, for n => 8, f'(n) > 0, and that f(8) > 0. It would then follow that f(n) > 0 for n => 8.