Let k be a non negative integer and a and b are integers. Prove that 2^(2k)=a^2+b^2, then one of a and b is ze?
Let's prove it by contradiction but first recall: If a = 2r+1 is odd then a^2 = 4r(r+1) + 1 = 1 mod 4. This means if a^2 + b^2 = 0 mod 4 then both a and b must be even. ---------------------------------------... Let a, b and k satisfy a^2 + b^2 = 4^k with strictly positive a and b and k, and with least possible positive k (the case k = 0 is trivial). Then a^2 + b^2 = 4^k = 0 mod 4 ==> both a and b are even ==> (a/2)^2 + (b/2)^2 = 4^(k-1), contradicting the minimality of k given that (a/2) and (b/2) are also both positive. This implies a^2 + b^2 = 4^k is not solvable when a and b are both positive ==> either a or b = 0, and (say b = 0), a = 2^k. ---------------------------------------... You can prove this by induction as well. The case k = 0 ==> a^2 + b^2 = 1 ==> a or b = 0. Assume it's true through k = n, then let's show it's true for n+1. a^2 + b^2 = 4^(n+1) ==> a^2 + b^2 = 0 mod 4 ==> both a and b are even ==> (a/2)^2 + (b/2)^2 = 4^n. By the induction hypothesis either a/2 or b/2 = 0 ==> either a or b = 0 (say b = 0), and a = 2^(n+1). It's the same proof as the first - just dressed up a little differently.
Let n be an integer. prove that 2 divides (n^4-3) if and only if 4 divides (n^2 + 3)?
Since 3 is odd then n^4 - 3 is even (divisible by 2) only when n is odd. So n = 2m+1 for some integer m and n^2 + 3 = (2m+1)^2 +3 = 4m^2 + 4m + 1 + 3 = 4(m^2 +m +1) is divisible by 4. Now just work in reverse. If n^3+3 is divisible by 4 then n must be odd since 3 is. So n = 2m+1, and n^2+3 = 4(m^2+m+1) just as above, so there are no further conditions on m. Since n is odd then n^4-3 is even.
If [math]x[/math] and [math]y[/math] are non-negative odd integers, then prove that [math]x^2+y^2[/math] is not divisible by [math]4[/math]?
It's a bit easy.We know that an odd non-negative integer has the form 2k-1 , where k is non-zero positive integer.So let , x =2k-1 and y=2t-1Which immediately gives x^2=4(k^2-k)+1 &y^2=4(t^2-t)+1 . It's now easy to see that x^2+y^2=4(k^2+t^2-k-t)+2So, if you divide it by 4 it will give 2 as a remainder.
How do I prove by mathematical induction that, for any nonnegative integer [math]n[/math], [math]7^n - 2^n[/math] is divisible by [math]5[/math]?
Let [math]S(n)[/math] be the statement: [math]7^{n}-2^{n}[/math] is divisible by [math]5[/math]; [math]n\geq{0}[/math]Basis step: [math]S(0)[/math]: [math]7^{(0)}-2^{(0)}=0[/math], which is divisible by [math]5[/math]Inductive step:Assume [math]S(k)[/math] is true, i.e. assume that [math]7^{k}-2^{k}[/math] is divisible by [math]5[/math]; [math]k\geq{0}[/math][math]\hspace{62 mm}\Rightarrow 7^{k}-2^{k}=5A[/math]; [math]A\in\mathbb{N}[/math][math]\hspace{62 mm}\Rightarrow 7^{k}=5A+2^{k}[/math][math]S(k+1)[/math]: [math]7^{k+1}-2^{k+1}[/math][math]\hspace{14 mm}=7\cdot{7^{k}}-2\cdot{2^{k}}[/math][math]\hspace{14 mm}=7\cdot{\big(5A+2^{k}\big)}-2\cdot{2^{k}}[/math][math]\hspace{14 mm}=35A+7\cdot{2^{k}}-2\cdot{2^{k}}[/math][math]\hspace{14 mm}=35A+5\cdot{2^{k}}[/math][math]\hspace{14 mm}=5\hspace{1 mm}\big(7A+2^{k}\big)[/math], which is divisible by [math]5[/math].So [math]S(k+1)[/math] is true whenever [math]S(k)[/math] is true.Therefore, [math]7^{n}-2^{n}[/math] is divisible by [math]5[/math]; [math]n\geq{0}[/math].
Prove By Induction: 6 divides n^3-n whenever n is a nonnegative integer?
Prove By Induction: 6 divides n^3-n whenever n is a non-negative integer. First not that f(n) = n^3-n = n(n^2-1) = n(n-1)(n+1) For the case n = 1: f(1) = (1)(1 - 1)(1+1) = 0 = 6*B, for B = 0 so => 6 divides n^3-n, for n = 1. Now assume that 6 divides f(n) for n=1..k, now need to show that f(k+1) is also divisible by 6. f(k+1) = [k+1]([k+1]-1)([k+1]+1) = (k+1)k(k+2) = (k + 1)k([k -1] + 2 + 1) = (k + 1)k([k -1] + 3) =(k+1)k[k-1] + (k+1)k(3) = k(k-1)(k+1) + 3(k+1)k = f(k) + 3(k+1)k Since k(k+1) is always an even number, so can be written as 2L for some integer L => f(k+1) = 6B + 3*2L = 6B+6L = 6(B+L) = 6M. Since B and L are both integers, their sum M is an integer => f(k+1) is divisible by 6. Therefor by the induction hypothesis f(n) is divisible by 6 for all non-negative n.
Let Zn = integers mod n. Define [a] to be nilpotent if there exists some k such that [a]^k = [0].?
Since n has a perfect square factor (p), we let n = p^2 q for some p and some q. Let x = pq, now x is clearly in Zn (pq is less than p^2 q). Now we show that x is nilpotent by considering x^2: x^2 = (pq)^2 = p^2 q^2 Since n divides x^2, we know that x^2 mod n is zero and hence x is nilpotent.
Use induction to prove that 3 divides 2 ^2n - 1 for all positive integers n.?
Let P(n) = 2^2n - 1 i) Is it true for n = 1? That's obviously true. ii) Assume it is true for n = k Therefore, we have that P(k) = 2^2k - 1 = 3m for some integer m (thats what it means for it to be divisible by 3). Now, P(k + 1) = 2^[2(k + 1)] - 1 = 2^(2k + 2) - 1 = 4(2^2k) - 1; by exponent rules = 4(2^2k) - 1 + 4 - 4; adding and subtracting 4 which doesn't change anything. = 4(2^2k) - 4 + 3; grouping/adding terms in such a way that we can factor out a 4. = 4(2^2k - 1) + 3 = 4(3m) + 3; by the induction hypothesis = 3(4m + 1) That is clearly divisible by 3. Therefore, P(n) is divisible by 3 for all natural numbers n. Hope this helps! @Joshua H: LOL I just realized that mistake. Thanks for pointing it out :-)
What is the number of solutions of a+b+c=15 with non-negative integer values for a, b, and c?
TLDR: The formula given by Siddharth Mundada is correct, and for similar such questions, you can use it to determine the number of non-negative integer solutions.The general formula is (n+r-1)C(n-1) wherer= RHS of the equationn= number of variablesFor an understanding of how this formula can be explained, imagine the following scenario:You have 3 boxes, in which you have to place 15 identical items. In how many ways can you do this?Let _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ be the 15 itemsNow what we wish to do is insert two partitions | | so that these 15 items get divided into 3 boxes. Something like this:_ _ _ _ | _ _ _ _ _ _ _ | _ _ _ _ corresponding to (4,7,4)OR like this_ _ _ _ | _ _ _ _ _ _ _ _ _ _ _ | corresponding to (4,11,0)So you can basically insert a partition anywhere in the gaps between two items, including at the two extremes of the chain.--> You have 16 gaps to choose from initially in which you can place the first partition--> You have 17 gaps for the second partition to choose from after placing the first partitionHence no of ways= 16*17HoweverBy interchanging the 1st and the 2nd partition among themselves, we don't have new solutionsi.e _ _ _ _ 1 _ _ _ _ _ _ _ _ _ 2 _ _ is the same as_ _ _ _ 2 _ _ _ _ _ _ _ _ _ 1 _ _ Hence in general you have to divide by n! where n is the number of partitions in order to account for this.--> Answer= 16*17/2 = (15+3-1)C(3-1)
What is the shortcut to solve this problem? When positive integer n is divided by 3, the remainder is 2 and when n is divided by 5 , the remainder is 1. What is the least value of n?
The answer is 11.In such type of questions, one should always proceed with the bigger number. The first number which will leave a remainder of 1 when it is divided by 5 ( and is greater than 5) is 6. But 6 is completely divisible by 3. So 6 is not the answer. Next number which leaves a remainder of 1 when divided by 5 is 11. Also, 11 leaves a remainder of 2 when divided by 3. So 11 is the answer.So the shortcut? Proceed with the bigger number and the smaller number will ultimately fulfill its criteria itself.That's all.Arinjay Pathak.