practice problems

 Q1. Second principle of induction:

prove that for all natural numbers n, (3 + sqrt(5))^n + (3 - sqrt(5))^n is divisible by 2^n.

Let S_n = (3 + sqrt(5))^n + (3 - sqrt(5))^n

a = 3 + rt(5)
b = 3 - rt(5)

a+b = 6
ab = 4
a,b are roots of
x^2 - 6x + 4 = 0 => x^2 = 6x - 4
Multiply both sides with x^(n-1) =>
x^(n+1) = 6x^(n) - 4x^(n-1)
replace x with a,b and add them together
S_{n+1} = 6S_{n} - 4S_{n-1}
For n=1,2 Sn = 6,28, i.e. divisible by 2^1,2^2
Using second principle of induction assume it's true till S_{k} including S_{k-1} and below.
Then
S_{k+1} = 6S_{k} - 4S_{k-1}.
So it's divisible by 2^(k+1)
H.P.

Q2.
x + y = a + b
x^2 + y^2 = a^2 + b^2
Prove or disprove that x^n + y^n = a^n + b^n for all n >= 3.
S2.
We can prove it by induction but there is a simpler way.
(x+y)^2 = (a+b)^2 will give us xy = ab.

Let a,b be roots of:
t^2 -(a+b)t + ab = 0

And x,y be roots of:
t^2 -(x+y)t + xy = 0

Both these polynomials have same coefficients and hence they are same by definition.
=> Their roots are also same.
=> (a,b) = (x,y)
So x^n + y^n = a^n + b^n for all n >= 3
H.P.

Q3.
P(x) is a polynomial of degree 'n' s.t. P(x) = 2^x for x = 1,2,3... n+1. Find P(n+2).
S3.
2^x = (1+1)^x = xC0 + xC1 ... xCx
where xCr = x(x-1)(x-2)...(x-r)/r! a 'r' degree polynomial.
And xCr = 0 if x < r.

Now our plan is to construct a polynomial f(x) of degree 'n' s.t. it matches P(x) at n+1 points.
If so, then we will use Polynomial Identity Theorem which says that 2 polynomials of degree 'n' matching at (n+1) points are identical. For e.g. a line (degree 1 polynomial is uniquely defined using 2 points).
If P(x) - Q(x) = 0 at n+1 points even though they are n-degree => it's a zero polynomial hence they are same.

So, let's try to create a n-degree polynomial using
2^x = (1+1)^x = xC0 + xC1 ... xCx
which matches P(x) at n+1 points.
Let 
f(x) = xC0 + xC1 .. xCn
The last xCn is highest degree and its degree is 'n'. Why?
xCn = x(x-1)(x-2)...(x-n+1)/n!

f(1) = 1C0 + 1C1 + 0 + 0... = 2^1
f(2) = 2C0 + 2C1 + 2C2 + 0 + 0... = 2^2 [as soon as x becomes less than 'r', the terms become 0].
...
f(n) = 2^n
So far so good. f(x) and P(x) match at 'n' values.
But they need to match at (n+1) values.
f(n+1) = (n+1)C0 + (n+1)C1 ... + (n+1)Cn which is not equal to 2^(n+1).
So they don't match.

So will create another function g(x) like this:
g(x) = 2[(x-1)C0 + (x-1)C1 ... (x-1)Cn]
g(1) = 2[0C0 + 0 + 0...] = 2[2^0] = 2^1
g(2) = 2[1C0 + 1C1 + 0...] = 2[2^1] = 2^2
g(3) = 2[2C0 + 2C1 +2C2 + 0...] = 2[2^2] = 2^3
.....
g(n)  = 2[(n-1)C0 + (n-1)C1 .. (n-1)C(n-1) + (n-1)C(n)] = 2[2^(n-1)] = 2^n
similarly
g(n+1)  = 2[(n)C0 + (n)C1 .. (n)C(n-1) + (n)C(n)] = 2[2^(n)] = 2^(n+1)

So P(x) and g(x) both are 'n' degree polynomials matching at (n+1) values hence they are same.
So P(n+2) = g(n+2) = 2[(n+1)C0 + (n+1)C1 .. (n+1)C(n)] = 2[2^(n+1) - 1] = 2^(n+2) - 2 = answer
 



Comments

Post a Comment

Popular posts from this blog

Simon's factoring trick(complete the rectangle)

  "Complete the Rectangle" , also called Simon’s Favorite Factoring Trick , is a clever algebraic method for factoring expressions of the form: x y + a x + b y + c xy + ax + by + c Or more commonly, you'll see it used in a simpler form: x y + a x + b y + d xy + ax + by + d But especially when we’re given something like: x y + a x + b y + a b xy + ax + by + ab It becomes very easy to factor. Let me walk you through it step-by-step. 💡 The Key Idea We add and subtract a constant to turn the expression into a perfect rectangle (a.k.a. a factorable quadratic or product of binomials). The “complete the rectangle” version of this trick usually works best on expressions like: x y + a x + b y + a b xy + ax + by + ab We treat it like this: x y + a x + b y + a b = ( x + b ) ( y + a ) xy + ax + by + ab = (x + b)(y + a) ✅ Step-by-Step Example Factor: x y + 3 x + 2 y + 6 xy + 3x + 2y + 6 Step 1: Rearrange the terms: Group like this: x y + 3 x + 2 y + 6 xy + 3x + ...
Read more

IOQM 2023 solutions

Image
Q1. Let n be a positive integer such that 1 ≤ n ≤ 1000 . Let M n be the number of integers in the set X n = { 4 n + 1 , 4 n + 2 , … , 4 n + 1000 } . Let a = max ⁡ { M n : 1 ≤ n ≤ 1000 } , and b = min ⁡ { M n : 1 ≤ n ≤ 1000 } . a = \max\{M_n : 1 \leq n \leq 1000\}, \quad \text{and} \quad b = \min\{M_n : 1 \leq n \leq 1000\}. Find a − b a - b . Solution: Quick tip: If n^2 = k then (n+1)^2 = k + (2n + 1) We will use this here. Also as the numbers grow larger the gap between 2 perfect squares becomes less and less. For. e.g. there are 10 perfect squares between 1 and 100 but only 4 perfect squares between 101 and 200. So X1 = {sqrt(5) ... sqrt(1004)} will have the most number of perfect squares. While X1000 = {sqrt(4001)...sqrt(5000)} will have the least. In X1 the first integer square root is 3 and we know that 1024 is the square of 32 so the last integer will be 31. Total: 31 - 3 + 1 = 29 integers in X1. In X1000, We know that 64^2 = 4096 so 64 is the first integer. 70^2 = 4900 and ...
Read more

IOQM 2024 Paper solutions (Done 1-21, 29)

Image
Q1 (number-theory). The smallest positive integer that does not divide 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 is: Solution : This product has all the integers from 1 to 9. So smallest integer not dividing it would be the next prime after 9. Which is 11. Answer: 11 Q2 (combinatorics): The number of four-digit odd numbers having digits 1, 2, 3, 4, each occurring exactly once, is: Solution: Last digit has to be 1 or 3: 2C1 Choosing remaining 3 digits: 3C3 Arranging those 3 digits: 3! Answer: 2C1*3C3*3! = 12 Q3 (number-theory): The number obtained by taking the last two digits of \(5^{2024}\) in the same order is: Solution: To get last 2 digits from number, divide by 100 and take the remainder. So we have to compute mod 100. 25 mod 100 = 25 25.5 mod 100 = 125 mod 100 = 25 5^3.5 mod 100 = 25.5 mod 100 = 25 5^4.5 mod 100 = 25.5 mod 100 = 25 ..... So: 5^2024 mod 100 = 25. Q4 (geometry): Let ABCD be a quadrilateral with \(\angle ADC = 70^\circ\), \(\angle ACD = 70^\circ\), \(\angle ACB = 10^\circ\...
Read more