A challenge! (1 Viewer)

[Grey Council]

Hokay, I just finished doing the hardest 3u induction question I've EVER done.

:-\

Here it is, for the guys who want a challenge. Although the 4u guys should be able to do this with ease, i think.

prove for all positive integral n:
7^n + 3n(7^n) - 1 is divisible by 9

*faints with exhaustion*

if you need help, ask. hehe
*runs off to do some more revision*

 

[Estel]

EDIT: SOLUTION AHEAD, DO NOT READ IF YOU WISH TO ATTEMPT Q


7^n + 3n(7^n) - 1 is divisible by 9

A.
When n=1
LHS = 7^n + 3n(7^n) - 1
= 7 + 21 - 1
= 27, which is divisible by 9.

B.
Suppose that the statement is true for n=k.
That is, suppose that 7^k + 3k(7^k) - 1 = 9m, for some integer m.
We prove the statement is true for n=k+1
That is, we prove 7^(k+1) + 3(k+1)(7^(k+1)) - 1 is divisible by 9.
Now 7^(k+1) + 3(k+1)(7^(k+1)) - 1= (7^(k+1)) (3k+4) - 1
= 7(7^k)(3k+4) - 1
= 7[(7^k)(3k+1) - 1] + 21*7^k + 6
= 63m + 21*7^k + 6*7^k +18k(7^k) - 54m, by the induction hypothesis.
= 9m + 27*7^k +18k(7^k)
= 9[m+3*7^k+2k(7^k)], which is divisible by 9 as required.

C.
It follows from parts A and B by mathematical induction that the statement is true for all positive integers n.

 

[Grey Council]

You could have hidden the answer.

:-\

now people won't attempt to do the question, just look at the solution.


ah well, well done Estel. hehe, I got confused for a while.

 

[Estel]

Sorry bout that, edited to warn people not to read if they wish to try the Q.

 

[:: ck ::]

grey council post up sum harder induction q's today is my induction revision day !

 

[shkspeare]

1. The cube of the sum of three consecutive integers is divisible by 3

2. The sum of the angles of a polygon of n sides is (2n-4) right angles, n >=2

3. The greatest number of regions that n straight lines can divide a circle is

1/2(n^2 + n + 2), n>=1

 

[Estel]

Answers: Do not read ahead if you intend on doing the questions.

1. The cube of the sum of three consecutive integers is divisible by 3
Statement: (n-1)^3+n^3+(n+1)^3 is divisible by 3.

A.
When n=1,
(n-1)^3+n^3+(n+1)^3 = 1^3 + 2^3
= 9, which is divisible by 3.
So the statement is true for n=1.

B.
Suppose that the statement is true for n = k
That is, suppose that (k-1)^3+k^3+(k+1)^3 = 3m, for some integer m.
The proof will be done in two parts.
Firstly, we prove the statement is true for n = k+1
That is, we prove that k^3 + (k+1)^3 + (k+2)^3 is divisible by 3.
k^3 + (k+1)^3 + (k+2)^3
= 3m + (k+2)^3 - (k-1)^3, by the induction hypothesis.
= 3(m+3k^2+9k+3), which is divisible by 3, as required.
Secondly, we prove the statement is true for n = k-1
That is, we prove that (k-2)^3 + (k-1)^3 + k^3 is divisible by 3.
(k-2)^3 + (k-1)^3 + k^3
= 3m + (k-2)^3 - (k+1)^3, by the induction hypothesis.
= 3(m-3k^2+3k-3), which is divisible by 3, as required.

C.
It follows from parts A and B by mathematical induction that the statement is true for all integers n.

Hence, the cube of the sum of three consecutive integers is divisible by 3.



2. Haven't done geometrical induction. :/ Still giving a go to 3...



3. The greatest number of regions that n straight lines can divide a circle is
(n^2 + n + 2)/2, n>=1
A.
When n=1
(n^2 + n + 2)/2 = 4/2
= 2.
So the statement is true for n = 1.
B.
Now the nth line will create n new regions at most if and only if it cuts n lines internally.
So, suppose that the statement is true for n=k.
That is, suppose (k^2 + k + 2)/2 = 1 + 1 + 2 + 3+ ... + k
We prove the statement is true for n=k+1
That is, we prove that ((k+1)^2 + k + 3)/2 = 1 + 1 + 2 + 3+ ... + k + (k+1)
LHS = ((k+1)^2 + k + 3)/2
= (k^2 + k + 2)/2 +1/2 + (2k+1)/2
= 1 + 1 + 2 + 3+ ... + k + (k+1), by the induction hypothesis.
= RHS
C.
It follows from parts A and B by mathematical induction that the statement is true for all positive integers n.

 

[Grey Council]

Hokay, in response on Ryan's request, I can do no better than post up questions given by the esteemed CM_Tutor.


http://www.boredofstudies.org/community/showpost.php?p=574016&postcount=29

 

[shkspeare]

thx estel!

still need help with :

2. The sum of the angles of a polygon of n sides is (2n-4) right angles, n >=2

and for the things u posted up grey council (do u go to my school? syd boys)

5. (a) Show that sin x + cos x = sqrt(2) * sin(x + pi / 4)

(b) Show that the derivative of y = e^xsin x is dy/dx = sqrt(2) * e^xsin(x + pi / 4)

(c) Given that y = e^xsin x, use mathematical induction to prove that the nth derivative for positive integral n is given by dⁿy/dxⁿ = [sqrt(2)]ⁿe^xsin(x + n * pi / 4)

i dont know how to do [c]

6. The Fibonacci sequence is a sequence of numbers defined by the following rules: F₁ = 1, F₂ = 1, and
F_n = F_n-1 + F_n-2 for integers n > 2.

(a) Write out the first 12 terms of the Fibonacci sequence

(b) Use mathematical induction to prove that F_3k is even, and that F_4k is a multiple of 3, for all positive integers k

(c) Hence, or otherwise, prove that F_12k is divisible by 6, for all integers k > 0


all of 6

8. Prove by induction that, for all positive integers n,
2 + (2 + 2²) + (2 + 2² + 2³) + ... + (2 + 2² + 2³ + ... + 2ⁿ) = 2ⁿ⁺² - 2(n + 2)

or 8 .. [does this have anything to do with geometric series?]

i have simplified the LHS as n[2(2^n-1)/(n-1)] .. but i cant seem to do the next step..


perhaps CM or anyone similar can give me hints???

 

[Grey Council]

yup, I go to Sydney Boys High.

You would be?

and heh, i'm done with maths for tonight. Will look at tommorow, if CM doesn't help you. You should post up what you got so far for the questions you need help with, cause no point in someone posting up the solution. Better if people see what you've done, and then give you a hint/nudge/correction/whatever.

 

[CM_Tutor]

1. The cube of the sum of three consecutive integers is divisible by 3
Statement: (n-1)^3+n^3+(n+1)^3 is divisible by 3.

Estel, whilst I agree that is probably what the question means, it is not what it says. Your statement is saying the sum of the cubes of three consecutive integers is divisible by three. The question said that the cube of the sum of three consecutive integers is divisible by three, and thus means that:

[n + (n + 1) + (n + 2)]³ is divisible by 3, where n is an integer

Note to all: Both of these theorems are much easier proved without induction, and you should avoid using induction if it is not mandated by the question.

Proof of originial question:
[n + (n + 1) + (n + 2)]³ = (3n + 3)³ = [3(n + 1)]³ = 27(n + 1)³
which is obviously divisible by 3.

Proof of Estel's version:
(n - 1)³ + n³ + (n + 1)³ = (n³ - 3n² + 3n - 1) + n³ + (n³ + 3n² + 3n + 1) = 3n³ + 6n = 3n(n² + 2)
which is divisible by 3.

 

[CM_Tutor]

2. The sum of the angles of a polygon of n sides is (2n-4) right angles, n >=2

I'm sure this has been discussed before, so do a search, and if you still can't find the answer, come back and I'll try to type it up.

 

[CM_Tutor]

5. (a) Show that sin x + cos x = sqrt(2) * sin(x + π / 4)

(b) Show that the derivative of y = e^xsin x is dy/dx = sqrt(2) * e^xsin(x + π / 4)

(c) Given that y = e^xsin x, use mathematical induction to prove that the nth derivative for positive integral n is given by dⁿy/dxⁿ = [sqrt(2)]ⁿe^xsin(x + nπ / 4)

i dont know how to do (c)

Theorem: If y = e^xsin x, then dⁿy/dxⁿ = [sqrt(2)]ⁿe^xsin(x + nπ / 4), for all positive integers n.

Proof: By induction on n:

A Put n = 1: LHS = dy/dx
= sqrt(2) * e^xsin(x + π / 4) by part (b) above
RHS = [sqrt(2)]¹e^xsin(x + 1 * π / 4)
= sqrt(2) * e^xsin(x + π / 4)
= LHS

So, the result is true for n = 1.

B Let k be a value of n for which the result is true.
That is, d^ky/dx^k = [sqrt(2)]^ke^xsin(x + kπ / 4) _____ (**)

We must now prove the result for n = k + 1.
That is, we must prove d^k+1y/dx^k+1 = [sqrt(2)]^k+1e^xsin[x + (k + 1)π / 4]

LHS = d^k+1y/dx^k+1
= d/dx[d^ky/dx^k]
= d/dx[[sqrt(2)]^ke^xsin(x + kπ / 4)], using the induction hypothesis (**)
= [sqrt(2)]^k * [sin(x + kπ / 4) * e^x + e^x * cos(x + kπ / 4)] * 1], using the Product Rule
= [sqrt(2)]^ke^x[sin(x + kπ / 4) + cos(x + kπ / 4)]
= [sqrt(2)]^ke^x * sqrt(2) * sin[x + (kπ / 4) + (π / 4)], using part (a) above
= [sqrt(2)]^k+1e^xsin[x + (k + 1)π / 4]
= RHS

So, if the result is true for n = k, then it is also true for n = k + 1.

C It follows from A and B by the process of mathematical induction that the result is true for all integers n ≥ 1

 

[CM_Tutor]

6. The Fibonacci sequence is a sequence of numbers defined by the following rules: F₁ = 1, F₂ = 1, and
F_n = F_n-1 + F_n-2 for integers n > 2.

(a) Write out the first 12 terms of the Fibonacci sequence

(b) Use mathematical induction to prove that F_3k is even, and that F_4k is a multiple of 3, for all positive integers k

(c) Hence, or otherwise, prove that F_12k is divisible by 6, for all integers k > 0

I'll start you off on this one, and you can see how you go.

(a) F₁ = 1
F₂ = 1
F₃ = F₂ + F₁ = 1 + 1 = 2
F₄ = F₃ + F₂ = 2 + 1 = 3
F₅ = F₄ + F₃ = 3 + 2 = 5
F₆ = F₅ + F₄ = 5 + 3 = 8

keep going, you should find that F₁₂ = 144

(b) F_3k ...
This is referring to the terms F₃, F₆, F₉, F₁₂, ...
You must prove that all such terms are even. Clearly the pattern holds for the first few terms (2, 8, 34, 144, ...). You are asked to use induction to prove that all such terms are even.

Similarly, show all F_4k are divisible by 3

(c) I'll leave you to ponder ...

 

[CM_Tutor]

8. Prove by induction that, for all positive integers n,
2 + (2 + 2²) + (2 + 2² + 2³) + ... + (2 + 2² + 2³ + ... + 2ⁿ) = 2ⁿ⁺² - 2(n + 2)

or 8 .. [does this have anything to do with geometric series?]

i have simplified the LHS as n[2(2^n-1)/(n-1)] .. but i cant seem to do the next step..

Yes, this does have something to do with geometric series, but that shouldn't come up until part B of the induction proof.

As for your simplification, there is definitely something wrong as the LHS must be an integer, but your expression is not an integer for n = 4, for example.

 

[CM_Tutor]

PS: I can probably find more induction questions, if people want them, including factorial induction and some 4u induction questions.

 

[Xayma]

I'll start you off on this one, and you can see how you go.

(a) F₁ = 1
F₂ = 1
F₃ = F₂ + F₁ = 1 + 1 = 2
F₄ = F₃ + F₂ = 2 + 1 = 3
F₅ = F₄ + F₃ = 3 + 2 = 5
F₆ = F₅ + F₄ = 5 + 3 = 8

keep going, you should find that F₁₂ = 144

That becomes tedious as you get going. If you can remember that F_n equals the nearest integer to φⁿ/√5, where φ is the golden ratio (1/2 (1+√5)) of course you probably wont remember it, but if you do it works well cause you then only have to change one number (the power) while having it on 0 dp.

*Solution to B and C, highlite to read (when I get the right color) *****
<font color="#D1D1E1">
b) F_3k

A)
At k=1
F₃=2
&there4; true for k=1

B) Assume true for k=j (I dont know what else to put here so "j" it is)
F_3j=2P, where P is an integer
ie F_3j-2+F_3j-1=2P

C) Prove true for k=j+1
F_3j+3=F_3j+1+F_3j+2
=F_3j+2-F_3j+F_3j+2
=2(F_3j+2)-2P
=2(F_3j+2-P)
Since F_3j+2 and P are integers, it is true for k=j+1 if k=j

F_4k
A) Prove true for k=1
F₄=3 &there4; true for k=1

B) Assume true for k=j
F_4j=3P where P is an integer

C) Prove true for k=j+1
F_4j+4=F_4j+2+F_4j+3
=F_4j+F_4j+1+F_4j+1+F_4j+2
=F_4j+F_4j+1+F_4j+1+F_4j+1+F_4j
=2F_4j+3F_4j+1
=2(3P)+3F_4j+1
=3(2P+F_4j+1)
Since P and F_4j+1 are integers, true for k=j+1, blah blah blah standard ending

part c)
F_12k
Let Q=4k, &there4; F_12k=F_4Q
&there4; F_4Q is divisible by 3 (as in part b)
similarly if R=4k, F_3R is divisible by 2
&there4;, F_12k is divisible by 3 and 2, &there4; it is a multiple of 3 and 2, ie it is a multiple of 6, &there4;, F_12k is divisible by 6
</font>
EDIT: There are only so many colours it could be

 

[:: ck ::]

golden ratio !!!

blah!! >.<" i gotz no idea wtf that is T_T

CM u rkn u cud post up wot is considered 4unit induction, and some challenge q's on applications of calculus to physical world ?

also how hard can sequences and series get? my assessment sheet says some crap about "harder applications of sequences and series..." as a topic under "harder 2unit"

most of the q's on sequences and series just seem to be using the formula =\

thx! u r a legend

 

[Xayma]

golden ratio !!!

blah!! >.<" i gotz no idea wtf that is T_T

The golden ratio is a cool number, &phi;²=&phi;+1, 1/&phi;=&phi;-1, as fibbonachi numbers get higher, F_n/F_n-1 approaches &phi;, and lots of cool other things

 

[Xayma]

8. Prove by induction that, for all positive integers n,
2 + (2 + 2²) + (2 + 2² + 2³) + ... + (2 + 2² + 2³ + ... + 2ⁿ) = 2ⁿ⁺² - 2(n + 2)

Hmm I have an answer that looks dodgy, ie I use another induction to prove this induction inside it.

Humbug, I just figured out the geometrical series way, hmm well here is the original answer, Ill post the geometrical series way under it soon
****Highlight to read****
<font color="#D1D1E1">

A) Prove true for n=1

LHS=2
RHS=2³-6
=8-6
=2=LHS
&there4; true for n=1

B) Assume true for n=k
2 + (2 + 2²) + (2 + 2² + 2³) + ... + (2 + 2² + 2³ + ... + 2^k) = 2^k+2 - 2(k + 2)

C) Prove true for n=k+1
Ie trying to prove
2 + (2 + 2²) + (2 + 2² + 2³) + ... + (2 + 2² + 2³ + ... + 2^k)+(2 + 2² + 2³ + ... + 2^k)+2^k+1) = 2^k+3 - 2(k + 3)

Now 2 + (2 + 2²) + (2 + 2² + 2³) + ... + (2 + 2² + 2³ + ... + 2^k) = 2^k+2 - 2(k + 2) &there4; it is true if

(2 + 2² + 2³ + ... + 2^k+2^k+1) = 2^k+3 - 2(k + 3)-[2^k+2 - 2(k + 2)]
=2^k+3-2k-6-2^k+2+2k+4
=2*2^k+2-2^k+2-2
=2^k+2-2
Dividing both sides by 2 to make it look neater
2⁰+2¹+2²+....+2^k=2^k+1-1
&there4; it is true if the above is true

A₂)Prove true for k=1
LHS=1+2
=3
RHS=2²-1
=3=LHS &there4; true for k=1

B₂) Assume true for k=j
2⁰+2¹+2²+....+2^j=2^j+1-1

C₂) Prove true for k=j+1
2⁰+2¹+2²+....+2^j+2^j+1=2^j+1-1+2^j+1
RHS=2*2^j+1-1
=2^j+2-1
&there4; true for k=j+1, &there4; true for k=1, 2, 3,... and for all positive integers.

As 2⁰+2¹+2²+....+2^k=2^k+1-1 is true for all positive integers, 2 + (2 + 2²) + (2 + 2² + 2³) + ... + (2 + 2² + 2³ + ... + 2ⁿ) = 2ⁿ⁺² - 2(n + 2) is true for n=1, 2, 3 and for all n>0
</font>

********Geometrical applications way (2nd time Ive posted this, stupid error) *******<font color="#D1D1E1">
A) and B) are the same
C)
2 + (2 + 2²) + (2 + 2² + 2³) + ... + (2 + 2² + 2³ + ... + 2^k)+(2 + 2² + 2³ + ... + 2^k)+2^k+1) =
2(2¹-1)+2(2²-1)+2(2³-1)+.......+2(2^k-1)+2(2^k+1-1) [Each one is a geometric series, (r-1)=1]
=2(2+2²+2³+....+2^k+2^k+1-(k+1)) [yay another geometric series, and we had k+1 ones]
=2(2(2^k+1-1)-(k+1))
=2(2^k+2-k-1-2)
=2(2^k+2-(k+3))
=2^k+3-2(k+3)
&there4; true for n=k+1 and since true for n=1, true for n=2,3,4,5.... and for all n>0 </font>