Posts

practice problems pending

Image
 Q1. Prove that for every positive integer (n), the number [ 3^{3^n}+1 ] is the product of at least (2n+1) (not necessarily distinct) primes. S1. Prove by induction. Q2. Prove that for every positive integer (n), there exists an (n)-digit number divisible by (5^n) whose all digits are odd. S2. Proof by induction: Let's assume it holds true for k  Now we construct 5 (n+1) digit numbers using A: All 5 of them leave different remainders modulo 5 so at least one of them will leave 0 and that would give us divisibility by 5^(n+1). Why will all be different modulo 5? Let's try to prove by contradiction: 2^n + a = 3.2^n + a mod 5 => 2.2^n = 0 mod 5 false. And each time you do this you will get some even number = 0 mod 5. Which is false. H.P. Q3. Let n be a positive integer. Let 0 < a1 < a2 ... an be real numbers. Prove that at least {n+1}C{2}) of the sums +-a1 +-a2 ... +-an are distinct. S3. First we will show that this problem maps to another simpler problem. And then solve...
Post a Comment
Read more

practice problems

Image
Q1. Show that (1 - 1/2^2)(1 - 1/3^2)....(1 - 1/(n+1)^2) = n+2/2n+2 S1. Easy to show via induction. Other way via telescopic cancellations: Kth term is (k^2 - 1)/k^2 = (k-1)(k+1)/k^2 = (k-1)/k.(k+1)/k Now separate out k-1/k and k+1/k terms and multiply: 2-1/2 * 3-1/3 * 4-1/4 .... n/n+1 = 1/n+1 2+1/2 * 3+1/3 ... n+2/n+1 = n+2/2 Hence proved. Q2. Show that: S2. Short method: r*nCr = n*(n-1)C(r-1) and take sigma simply. Longer method:  2^(n-1) = (n-1)C0 + (n-1)C1... (n-1)C(n-1) (n-1)Ck *n = nCk*(n-k) How? n * (n-1)!/k!(n-1-k)! = n! /k!(n-k-1)! But (n-k-1)! = (n-k)!/(n-k) So n * (n-1)!/k!(n-1-k)! = (n-k)n! /k!(n-k)! = nCk*(n-k) So n*2^(n-1) = n *2^(n-1) = n*[(n-1)C0 + (n-1)C1... (n-1)C(n-2)+ (n-1)C(n-1)] = nC0 * (n-0) + nC1*(n-1) ... nC(n-2)*(2)+ nC(n-1)*(1) It can be rewritten as: = nCn*n + nC1 * (n-1) ... nC2 * 2 + nC1 * 1 = (r = 1 to n)Sigma(r*nCr) = (r = 0 to n)Sigma(r*nCr) Hence proved. Q3. S3. Quite simple. Let the given sum be S. 3S = 1.3^2 + 2.3^3... n.3^(n+1) S-3S = 3 + 3^2 ......
Post a Comment
Read more

practice problems

Q1. Prove that: 1/15 <  1.3.5.7...99/2.4.6.8...100  < 1/10 S1. We will use the property that n/n+1 < n+1/n+2 i.e. as the integer 'k' increases k/k+1 keeps becoming larger. It is easy to prove it by cross multiplication: n(n+2) < (n+1)^2 => 0 < 1. Let's rewrite it as: 1/2 * 3/4 * 5/6 ... 99/100 = P Let Q = 2/3 * 4/5 ....98/99 * 100/101 Both P,Q have 50 fractions each. And each fraction of P is less than its corresponding fraction in Q. So P < Q Multiply both sides by P. P^2 < PQ = 1/2 * 2/3 * 3/4 .... 100/101 = 1/101 P^2 < 1/101 => P^2 < 1/100 => P < 1/10 Now for the other part where we have to prove that P > 1/15 P = 1/2 *(3/4 * 5/6 * ... 99/100) R = 2/3 * 4/5 ... 98/99 => P > R/2 2P> R 2P^2 > P.R = 1/2 * 2/3 * 3/4 ... 99/100 = 1/100 P^2 > 1/200 P^2 > 1/225 P > 1/15 H.P.
Post a Comment
Read more

linear algebra homework

Image
Q1.  S1. A is 3x2 so B will be 2x3. Rank(A) = 2 so it's possible to create I2 which has rank 2. Now let B = a b c, d e f Now when we multiply BA and equate with I2 we will have 4 equations for 6 variables. So 2 variables will be free and hence there will be infinite such matrices. Rank(I_3) = 3 Rank(AC) = min(Rank(A),Rank(C) = 2 So it's not possible since ranks don't match. Q2. Prove that a square row echelon matrix M is either the identity matrix I, or else its bottom row is zero. S2. If we start with the top left element as the first pivot element, then each subsequent row needs to have the pivot element to its right. So if we keep shifting the column and row by 1 we will just manage to take row echelon matrix by using the bottom left element. If at any step we take more than 1 step right, than one or more rows at bottom will have to be zero rows. Q3. S3. We need to convert the given matrix to Identity matrix. It is possible since both columns are independent. R2 - 2R...
Post a Comment
Read more

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. =...
Post a Comment
Read more

practice problems pending

Image
S1. Let a = sqrt(2014) => 4029 = 2a^2 + 1 Equation becomes: ax^3 - (2a^2 + 1).x^2 + 2 = 0 ax^3 - x^2 - 2a^2.x^2  + 2 = 0 x^2(ax -1) - 2(a^2x^2 - 1) = 0 x^2(ax -1) - 2(ax + 1)(ax - 1) = 0 (ax - 1)(x^2 - 2ax - 2) = 0 x = 1/a is one root. x^2 - 2ax - 2 = 0 gives x = [2a +-sqrt(4a^2 + 8)]/2 = a +- sqrt(a^2 + 2) So the 3 roots are: a > 1 1/a (middle) a + sqrt(2 + a^2) (biggest) a - sqrt(2 + a^2) (smallest since negative) So x2 = 1/a Answer = 2 Q2. S2. Take 4 to LHS and get: x/x-3 + x/x-5 ... = x^2 - 11x => x = 0 is one solution => x/x-3 + x/x-5 ... = x - 11 Now combine 3,19 and 5,17 terms 1/x-3 + 1/x-19 = 2x - 22/(x-3)(x-19) 1/x-5 + 1/x-17 = 2x - 22/(x-5)(x-17) => 2(x-11)[1/(x-3)(x-19) + 1/(x-5)(x-17)] = x-11 => x = 11 is another root. Now 1/(x-3)(x-19) + 1/(x-5)(x-17) = 1/2 1/(x^2 - 22x + 57) + 1/(x^2 - 22x + 85) = 1/2 Let x^2 - 22x + 57 = u => 1/u + 1/(u + 28) = 1/2 => 2(2u + 28) = u^2 + 28u = 4u + 56 => u^2 + 24u - 56 = 0 u = [-24 +-sqrt(24*24 + 4*56)]/2...
Post a Comment
Read more

practice problems

Q1. For any integer a, show the following: (a) gcd(2a+1,9a+4)=1. (b) gcd(5a+2,7a+3)=1. (c) If a is odd, then gcd(3a,3a+2)=1.  S1. (a) Using Euclid algorithm: (2a+1,9a+4) = (2a+1,a) = (1,a) = 1 (b) (5a+2,7a+3) = (5a+2,2a+1) = (a,2a+1) = (a,1) = 1 (c) (3a,3a+2) = (3a,2) Since 3a is odd => gcd = 1 Q2. If  a∣bc, then show that a∣ gcd(a,b) gcd(a,c) S2. Using Bezout's identity: gcd(a,b) = d1 = m1a + m2b gcd(a,c) = d2 = n1a + n2c d1.d2 = m1.n1.a^2 + m1.n2.ac + n1m2ab + m2n2bc We need to show that d1d2 = ak. Each term in d1.d2 is div by a except m2n2bc but we know that bc is div by a. H.P. Q3. Use the Euclidean Algorithm to obtain integers x and y s.t. (a)  gcd(56,72)=56x+72y. (b) gcd(24,138)=24x+138y. (c) gcd(119,272)=119x+272y. (d) gcd(1769,2378)=1769x+2378y. S3. (a) (56,72) = (56,72-56.1=16) = (56-16*3 = 8,16) = 8 8 = 56-(72 - 56.1)*3  = 56*4 - 3*72 = 224-216 (b) gcd(24,138) = 24,138-24*5 = 24,18 = 24-18,18 = 6,18 = 6 (138-24*5)*(-1) + 24 = 24*6 - 138*1 = 144-138 ...
Post a Comment
Read more