https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Sirhcgninil&feedformat=atomAoPS Wiki - User contributions [en]2024-03-28T11:03:46ZUser contributionsMediaWiki 1.31.1https://artofproblemsolving.com/wiki/index.php?title=Lagrange%27s_Identity&diff=130093Lagrange's Identity2020-08-01T14:04:52Z<p>Sirhcgninil: </p>
<hr />
<div>In algebra, Lagrange's identity, named after Joseph Louis Lagrange, is:[1][2]<br />
<br />
<cmath>{{\begin{aligned}{\biggl (}\sum _{k=1}^{n}a_{k}^{2}{\biggr )}{\biggl (}\sum _{k=1}^{n}b_{k}^{2}{\biggr )}-{\biggl (}\sum _{k=1}^{n}a_{k}b_{k}{\biggr )}^{2}&=\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}(a_{i}b_{j}-a_{j}b_{i})^{2}\\&{\biggl (}={\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1,j\neq i}^{n}(a_{i}b_{j}-a_{j}b_{i})^{2}{\biggr )},\end{aligned}}} </cmath><br />
<cmath>\begin{align}<br />
\biggl( \sum_{k=1}^n a_k^2\biggr) \biggl(\sum_{k=1}^n b_k^2\biggr) - \biggl(\sum_{k=1}^n a_k b_k\biggr)^2 & = \sum_{i=1}^{n-1} \sum_{j=i+1}^n (a_i b_j - a_j b_i)^2 \\<br />
& \biggl(= \frac{1}{2} \sum_{i=1}^n \sum_{j=1,j\neq i}^n (a_i b_j - a_j b_i)^2\biggr),<br />
\end{align}</cmath><br />
which applies to any two sets <math>\{a_1, a_2, . . ., a_n\}</math> and <math>\{b_1, b_2, . . ., b_n\}</math> of real or complex numbers.<br />
<br />
<br />
Proof:<br />
The vector form follows from the Binet-Cauchy identity by setting ci = ai and di = bi. The second version follows by letting ci and di denote the complex conjugates of ai and bi, respectively,<br />
<br />
Here is also a direct proof.[10] The expansion of the first term on the left side is:<br />
<br />
(1) {\left(\sum _{k=1}^{n}a_{k}^{2}\right)\left(\sum _{k=1}^{n}b_{k}^{2}\right)=\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}^{2}b_{j}^{2}=\sum _{k=1}^{n}a_{k}^{2}b_{k}^{2}+\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}a_{i}^{2}b_{j}^{2}+\sum _{j=1}^{n-1}\sum _{i=j+1}^{n}a_{i}^{2}b_{j}^{2}\ ,} \left( \sum_{k=1}^n a_k^2\right) \left(\sum_{k=1}^n b_k^2\right) = <br />
\sum_{i=1}^n \sum_{j=1}^n a_i^2 b_j^2 <br />
= \sum_{k=1}^n a_k^2 b_k^2 <br />
+ \sum_{i=1}^{n-1} \sum_{j=i+1}^n a_i^2 b_j^2 <br />
+ \sum_{j=1}^{n-1} \sum_{i=j+1}^n a_i^2 b_j^2 \ ,<br />
which means that the product of a column of as and a row of bs yields (a sum of elements of) a square of abs, which can be broken up into a diagonal and a pair of triangles on either side of the diagonal.<br />
<br />
The second term on the left side of Lagrange's identity can be expanded as:<br />
<br />
(2) {\left(\sum _{k=1}^{n}a_{k}b_{k}\right)^{2}=\sum _{k=1}^{n}a_{k}^{2}b_{k}^{2}+2\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}a_{i}b_{i}a_{j}b_{j}\ ,} \left(\sum_{k=1}^n a_k b_k\right)^2 = <br />
\sum_{k=1}^n a_k^2 b_k^2 + 2\sum_{i=1}^{n-1} \sum_{j=i+1}^n a_i b_i a_j b_j \ ,<br />
which means that a symmetric square can be broken up into its diagonal and a pair of equal triangles on either side of the diagonal.<br />
<br />
To expand the summation on the right side of Lagrange's identity, first expand the square within the summation:<br />
<br />
{\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}(a_{i}b_{j}-a_{j}b_{i})^{2}=\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}(a_{i}^{2}b_{j}^{2}+a_{j}^{2}b_{i}^{2}-2a_{i}b_{j}a_{j}b_{i}).} \sum_{i=1}^{n-1} \sum_{j=i+1}^n (a_i b_j - a_j b_i)^2 = \sum_{i=1}^{n-1} \sum_{j=i+1}^n (a_i^2 b_j^2 + a_j^2 b_i^2 - 2 a_i b_j a_j b_i). <br />
Distribute the summation on the right side,<br />
<br />
{\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}(a_{i}b_{j}-a_{j}b_{i})^{2}=\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}a_{i}^{2}b_{j}^{2}+\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}a_{j}^{2}b_{i}^{2}-2\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}a_{i}b_{j}a_{j}b_{i}.} \sum_{i=1}^{n-1} \sum_{j=i+1}^n (a_i b_j - a_j b_i)^2 = \sum_{i=1}^{n-1} \sum_{j=i+1}^n a_i^2 b_j^2 + \sum_{i=1}^{n-1} \sum_{j=i+1}^n a_j^2 b_i^2 - 2 \sum_{i=1}^{n-1} \sum_{j=i+1}^n a_i b_j a_j b_i .<br />
Now exchange the indices i and j of the second term on the right side, and permute the b factors of the third term, yielding:<br />
<br />
(3) {\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}(a_{i}b_{j}-a_{j}b_{i})^{2}=\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}a_{i}^{2}b_{j}^{2}+\sum _{j=1}^{n-1}\sum _{i=j+1}^{n}a_{i}^{2}b_{j}^{2}-2\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}a_{i}b_{i}a_{j}b_{j}\ .} \sum_{i=1}^{n-1} \sum_{j=i+1}^n (a_i b_j - a_j b_i)^2 = \sum_{i=1}^{n-1} \sum_{j=i+1}^n a_i^2 b_j^2 + \sum_{j=1}^{n-1} \sum_{i=j+1}^n a_i^2 b_j^2 - 2 \sum_{i=1}^{n-1} \sum_{j=i+1}^n a_i b_i a_j b_j \ .<br />
Back to the left side of Lagrange's identity: it has two terms, given in expanded form by Equations ('1') and ('2'). The first term on the right side of Equation ('2') ends up canceling out the first term on the right side of Equation ('1'), yielding<br />
<br />
('1') - ('2') = {\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}a_{i}^{2}b_{j}^{2}+\sum _{j=1}^{n-1}\sum _{i=j+1}^{n}a_{i}^{2}b_{j}^{2}-2\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}a_{i}b_{i}a_{j}b_{j}} \sum_{i=1}^{n-1} \sum_{j=i+1}^n a_i^2 b_j^2 <br />
+ \sum_{j=1}^{n-1} \sum_{i=j+1}^n a_i^2 b_j^2 - 2\sum_{i=1}^{n-1} \sum_{j=i+1}^n a_i b_i a_j b_j <br />
which is the same as Equation ('3'), so Lagrange's identity is indeed an identity,</div>Sirhcgninilhttps://artofproblemsolving.com/wiki/index.php?title=Fermat%27s_Little_Theorem&diff=110357Fermat's Little Theorem2019-10-16T14:16:11Z<p>Sirhcgninil: </p>
<hr />
<div>'''Fermat's Little Theorem''' is highly useful in [[number theory]] for simplifying the computation of exponents in [[modular arithmetic]] (which students should study more at the introductory level if they have a hard time following the rest of this article). This theorem is credited to [[Pierre de Fermat]].<br />
<br />
<br />
== Statement ==<br />
<br />
If <math>{a}</math> is an [[integer]], <math>{p}</math> is a [[prime number]] and <math>{a}</math> is not [[divisibility|divisible]] by <math>{p}</math>, then <math>a^{p-1}\equiv 1 \pmod {p}</math>.<br />
<br />
A frequently used corollary of Fermat's Little Theorem is <math> a^p \equiv a \pmod {p}</math>. As you can see, it is derived by multipling both sides of the theorem by <math>a</math>. The restated form is nice because we no longer need to restrict ourselves to integers <math>{a}</math> not divisible by <math>{p}</math>.<br />
<br />
This theorem is a special case of [[Euler's Totient Theorem]], which states that if <math>a</math> and <math>n</math> are integers, then <math>a^{\varphi(n)} \equiv 1 \pmod{n}</math>, where <math>\varphi(n)</math> denotes [[Euler's totient function]]. In particular, <math>\varphi(p) = p-1</math> for prime numbers <math>p</math>. In turn, this is a special case of [[Lagrange's Theorem]].<br />
<br />
In contest problems, Fermat's Little Theorem is often used in conjunction with the [[Chinese Remainder Theorem]] to simplify tedious calculations.<br />
<br />
== Proof ==<br />
We offer several proofs using different techniques to prove the statement <math>a^p \equiv a \pmod{p}</math>. If <math>\text{gcd}\,(a,p) = 1</math>, then we can cancel a factor of <math>a</math> from both sides and retrieve the first version of the theorem. <br />
<br />
=== Proof 1 (Induction) ===<br />
<br />
The most straightforward way to prove this theorem is by by applying the [[induction]] principle. We fix <math>p</math> as a prime number. The base case, <math>1^p \equiv 1 \pmod{p}</math>, is obviously true. Suppose the statement <math>a^p \equiv a \pmod{p}</math> is true. Then, by the [[binomial theorem]], <br />
<br />
<center><cmath>(a+1)^p = a^p + {p \choose 1} a^{p-1} + {p \choose 2} a^{p-2} + \cdots + {p \choose p-1} a + 1.</cmath></center><br />
<br />
Note that <math>p</math> divides into any binomial coefficient of the form <math>{p \choose k}</math> for <math>1 \le k \le p-1</math>. This follows by the definition of the binomial coefficient as <math>{p \choose k} = \frac{p!}{k! (p-k)!}</math>; since <math>p</math> is prime, then <math>p</math> divides the numerator, but not the denominator. <br />
<br />
Taken <math>\mod p</math>, all of the middle terms disappear, and we end up with <math>(a+1)^p \equiv a^p + 1 \pmod{p}</math>. Since we also know that <math>a^p \equiv a\pmod{p}</math>, then <math>(a+1)^p \equiv a+1 \pmod{p}</math>, as desired. <br />
<br />
=== Proof 2 (Inverses) ===<br />
<br />
Let <math>S = \{1,2,3,\cdots, p-1\}</math>. Then, we claim that the set <math>a \cdot S</math>, consisting of the product of the elements of <math>S</math> with <math>a</math>, taken modulo <math>p</math>, is simply a permutation of <math>S</math>. In other words, <br />
<br />
<center><cmath>S \equiv \{1a, 2a, \cdots, (p-1)a\} \pmod{p}.</cmath></center><br><br />
<br />
Clearly none of the <math>ia</math> for <math>1 \le i \le p-1</math> are divisible by <math>p</math>, so it suffices to show that all of the elements in <math>a \cdot S</math> are distinct. Suppose that <math>ai \equiv aj \pmod{p}</math> for <math>i \neq j</math>. Since <math>\text{gcd}\, (a,p) = 1</math>, by the cancellation rule, that reduces to <math>i \equiv j \pmod{p}</math>, which is a contradiction. <br />
<br />
Thus, <math>\mod{p}</math>, we have that the product of the elements of <math>S</math> is <br />
<br />
<center><cmath>1a \cdot 2a \cdots (p-1)a \equiv 1 \cdot 2 \cdots (p-1) \pmod{p}.</cmath></center> <br><br />
<br />
Cancelling the factors <math>1, 2, 3, \ldots, p-1</math> from both sides, we are left with the statement <math>a^{p-1} \equiv 1 \pmod{p}</math>.<br><br />
<br />
A similar version can be used to prove [[Euler's Totient Theorem]], if we let <math>S = \{\text{natural numbers relatively prime to and less than}\ n\}</math>.<br />
<br />
=== Proof 3 (Combinatorics) ===<br />
<center><asy> <br />
real r = 0.3, row1 = 3.5, row2 = 0, row3 = -3.5;<br />
void necklace(pair k, pen colors[]){<br />
draw(shift(k)*unitcircle); <br />
for(int i = 0; i < colors.length; ++i){<br />
pair p = k+expi(pi/2+2*pi*i/colors.length);<br />
fill(Circle(p,r),colors[i]);<br />
draw(Circle(p,r));<br />
}<br />
}<br />
<br />
pen BEADS1[] = {red,red,red},BEADS2[] = {blue,blue,blue},BEADS3[] = {red,red,blue},BEADS4[] = {blue,red,red},BEADS5[] = {red,blue,red},BEADS6[] = {blue,blue,red},BEADS7[] = {red,blue,blue},BEADS8[] = {blue,red,blue};<br />
necklace((-1.5,row1),BEADS1);necklace((1.5,row1),BEADS2);necklace((-2.5,row2),BEADS3);necklace((0,row2),BEADS4);necklace((2.5,row2),BEADS5);necklace((-2.5,row3),BEADS6);necklace((0,row3),BEADS7);necklace((2.5,row3),BEADS8);<br />
</asy><br> An illustration of the case <math>p=3,a=2</math>.<br></center><br />
<br />
Consider a necklace with <math>p</math> beads, each bead of which can be colored in <math>a</math> different ways. There are <math>a^p</math> ways to pick the colors of the beads. <math>a</math> of these are necklaces that consists of beads of the same color. Of the remaining necklaces, for each necklace, there are exactly <math>p-1</math> more necklaces that are rotationally equivalent to this necklace. It follows that <math>a^p-a</math> must be divisible by <math>p</math>. Written in another way, <math>a^p \equiv a \pmod{p}</math>.<br />
<br />
=== Proof 4 (Geometry) ===<br />
<center><asy><br />
void match(int i, int j){ <br />
draw(shift((i,j))*unitsquare,linewidth(1));<br />
draw(shift((j,i))*unitsquare,linewidth(1));<br />
draw((i+0.5,j+0.5)--(j+0.5,i+0.5),linewidth(2));<br />
}<br />
int n = 6;<br />
for(int i = 0; i < n; ++i){<br />
for(int j = 0; j < n; ++j)<br />
draw(shift((i,j))*unitsquare, linewidth(0.5));<br />
}<br />
draw((0,0)--(n,n),red+linewidth(2)); match(2,4); match(0,3);<br />
</asy>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<asy><br />
import three; currentprojection = perspective(3,-2,4);<br />
void match(int i, int j, int k){ <br />
draw(shift((i,j,k))*box((0,0,0),(1,1,1)),linewidth(1));<br />
draw(shift((k,i,j))*box((0,0,0),(1,1,1)),linewidth(1));<br />
draw(shift((j,k,i))*box((0,0,0),(1,1,1)),linewidth(1));<br />
draw((i+0.5,j+0.5,k+0.5)--(j+0.5,k+0.5,i+0.5)--(k+0.5,i+0.5,j+0.5)--cycle,linewidth(2));<br />
}<br />
int n = 4;<br />
for(int i = 0; i < n; ++i){<br />
for(int j = 0; j < n; ++j)<br />
for(int k = 0; k < n; ++k)<br />
draw(shift((i,j,k))*box((0,0,0),(1,1,1)), linewidth(0.5));<br />
}<br />
draw((0,0,0)--(n,n,n),red+linewidth(2));match(2,3,1); </asy>For <math>p=2,3</math> and <math>a=6,4</math>, respectively.</center><br />
We imbed a [[hypercube]] of side length <math>a</math> in <math>\mathbb{R}^p</math> (the <math>p</math>-th dimensional [[Euclidean space]]), such that the vertices of the hypercube are at <math>(\pm a/2,\pm a/2, \ldots, \pm a/2)</math>. A hypercube is essentially a cube, generalized to higher dimensions. This hypercube consists of <math>a^p</math> separate unit hypercubes, with centers consisting of the points <br />
<br />
<center><cmath>P(x_1, x_2, \ldots, x_n) = \left(a + \frac 12 - x_1, a + \frac 12 - x_2, \ldots, a + \frac 12 - x_p\right),</cmath></center><br><br />
<br />
where each <math>x_i</math> is an integer from <math>1</math> to <math>a</math>. Besides the <math>a</math> centers of the unit hypercubes in the main diagonal (from <math>(-a/2, -a/2, \ldots, -a/2)</math> to <math>(a/2, a/2, \ldots, a/2)</math>), the transformation carrying <br />
<br />
<cmath>P(x_1, x_2, \ldots, x_n) \mapsto P(x_2, x_3, \ldots, x_n, x_1)</cmath><br><br />
<br />
maps one unit hypercube to a distinct hypercube. Much like the combinatorial proof, this splits the non-main diagonal unit hypercubes into groups of size <math>p</math>, from which it follows that <math>a^p \equiv a \pmod{p}</math>. Thus, we have another way to visualize the above combinatorial proof, by imagining the described transformation to be, in a sense, a rotation about the main diagonal of the hypercube.<br />
<br />
== Problems ==<br />
=== Introductory ===<br />
* Compute some examples, for example find <math>3^{31} \pmod{7}, 29^{25} \pmod{11}</math>, and <math>128^{129} \pmod{17}</math>, and check your answers by calculator where possible.<br />
<br />
* Let <math>k = 2008^2 + 2^{2008}</math>. What is the units digit of <math>k^2 + 2^k</math>? ([[2008 AMC 12A Problems/Problem 15]])<br />
<br />
* Find <math>2^{20} + 3^{30} + 4^{40} + 5^{50} + 6^{60}</math> mod <math>7</math>. ([http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=207352162&t=304326 Discussion]).<br />
<br />
=== Intermediate ===<br />
* One of Euler's conjectures was disproved in the 1960s by three American mathematicians when they showed there was a positive integer such that <math>133^5+110^5+84^5+27^5=n^5</math>. Find the value of <math>{n}</math>. ([[1989 AIME Problems/Problem 9|1989 AIME, #9]])<br><br><br />
<br />
*If <math>f(x) = x^{x^{x^x}}</math>, find the last two digits of <math>f(17) + f(18) + f(19) + f(20)</math>. ([https://pumac.princeton.edu/info/archives/pumac-2008/ 2008 PUMaC, NT A#5])<br />
<br />
=== Advanced ===<br />
*Is it true that if <math>p</math> is a prime number, and <math>k</math> is an integer <math>2 \le k \le p</math>, then the sum of the products of each <math>k</math>-element subset of <math>\{1, 2, \ldots, p\}</math> will be divisible by <math>p</math>? <br><br><br />
<br />
== Hints/Solutions ==<br />
Introductory: <br />
* Hint: For the first example, we have <math>3^6 \equiv 1 \pmod{7}</math> by FLT (Fermat's Little Theorem). It follows that <math>3^{31} = 3 \cdot 3^{30} = 3 \cdot \left(3^{6}\right)^5 \equiv 3 \cdot 1^5 \equiv 3 \pmod{7}</math>.<br />
<br />
Intermediate:<br />
* Solution (1989 AIME, 9) To solve this problem, it would be nice to know some information about the remainders <math>n</math> can have after division by certain numbers. By Fermat's Little Theorem, we know <math>{n^{5}}</math> is congruent to <math>n</math> [[modulo]] 5. Hence,<br><br />
<center><math>3 + 0 + 4 + 7 \equiv n\pmod{5}</math></center><br />
<center><math>4 \equiv n\pmod{5}</math></center><br />
<br><br><br />
:Continuing, we examine the equation modulo 3,<br />
<center><math>-1 + 1 + 0 + 0 \equiv n\pmod{3}</math></center><br />
<center><math>0 \equiv n\pmod{3}</math></center><br />
<br />
<br><br><br><br />
:Thus, <math>n</math> is divisible by three and leaves a remainder of four when divided by 5. It's obvious that <math>n>133</math>, so the only possibilities are <math>n = 144</math> or <math>n = 174</math>. It quickly becomes apparent that 174 is much too large, so <math>n</math> must be 144.<br />
<br />
Advanced:<br />
* Hint: try to establish the identity <math>x^{p} - x \equiv x(x-1)(x-2) \cdots (x-(p-1)) \pmod{p}</math>, and then apply [[Vieta's formulas]]. <br />
<br />
== See also ==<br />
* [[Number theory]]<br />
* [[Modular arithmetic]]<br />
* [[Euler's Totient Theorem]]<br />
* [[Order (group theory)]]<br />
<br />
[[Category:Number theory]]<br />
[[Category:Theorems]]</div>Sirhcgninilhttps://artofproblemsolving.com/wiki/index.php?title=Fermat%27s_Little_Theorem&diff=110356Fermat's Little Theorem2019-10-16T14:13:54Z<p>Sirhcgninil: </p>
<hr />
<div>'''Fermat's Little Theorem''' is highly useful in [[number theory]] for simplifying the computation of exponents in [[modular arithmetic]] (which students should study more at the introductory level if they have a hard time following the rest of this article). This theorem is credited to [[Pierre de Fermat]].<br />
<br />
<br />
== Statement ==<br />
<br />
If <math>{a}</math> is an [[integer]], <math>{p}</math> is a [[prime number]] and <math>{a}</math> is not [[divisibility|divisible]] by <math>{p}</math>, then <math>a^{p-1}\equiv 1 \pmod {p}</math>.<br />
<br />
A frequently used corollary of Fermat's Little Theorem is <math> a^p \equiv a \pmod {p}</math>. As you can see, it is derived by multipling both sides of the theorem by <math>a</math>. The restated form is nice because we no longer need to restrict ourselves to integers <math>{a}</math> not divisible by <math>{p}</math>.<br />
<br />
This theorem is a special case of [[Euler's Totient Theorem]], which states that if <math>a</math> and <math>n</math> are integers, then <math>a^{\varphi(n)} \equiv 1 \pmod{n}</math>, where <math>\phi(n)</math> denotes [[Euler's totient function]]. In particular, <math>\phi(p) = p-1</math> for prime numbers <math>p</math>. In turn, this is a special case of [[Lagrange's Theorem]].<br />
<br />
In contest problems, Fermat's Little Theorem is often used in conjunction with the [[Chinese Remainder Theorem]] to simplify tedious calculations.<br />
<br />
== Proof ==<br />
We offer several proofs using different techniques to prove the statement <math>a^p \equiv a \pmod{p}</math>. If <math>\text{gcd}\,(a,p) = 1</math>, then we can cancel a factor of <math>a</math> from both sides and retrieve the first version of the theorem. <br />
<br />
=== Proof 1 (Induction) ===<br />
<br />
The most straightforward way to prove this theorem is by by applying the [[induction]] principle. We fix <math>p</math> as a prime number. The base case, <math>1^p \equiv 1 \pmod{p}</math>, is obviously true. Suppose the statement <math>a^p \equiv a \pmod{p}</math> is true. Then, by the [[binomial theorem]], <br />
<br />
<center><cmath>(a+1)^p = a^p + {p \choose 1} a^{p-1} + {p \choose 2} a^{p-2} + \cdots + {p \choose p-1} a + 1.</cmath></center><br />
<br />
Note that <math>p</math> divides into any binomial coefficient of the form <math>{p \choose k}</math> for <math>1 \le k \le p-1</math>. This follows by the definition of the binomial coefficient as <math>{p \choose k} = \frac{p!}{k! (p-k)!}</math>; since <math>p</math> is prime, then <math>p</math> divides the numerator, but not the denominator. <br />
<br />
Taken <math>\mod p</math>, all of the middle terms disappear, and we end up with <math>(a+1)^p \equiv a^p + 1 \pmod{p}</math>. Since we also know that <math>a^p \equiv a\pmod{p}</math>, then <math>(a+1)^p \equiv a+1 \pmod{p}</math>, as desired. <br />
<br />
=== Proof 2 (Inverses) ===<br />
<br />
Let <math>S = \{1,2,3,\cdots, p-1\}</math>. Then, we claim that the set <math>a \cdot S</math>, consisting of the product of the elements of <math>S</math> with <math>a</math>, taken modulo <math>p</math>, is simply a permutation of <math>S</math>. In other words, <br />
<br />
<center><cmath>S \equiv \{1a, 2a, \cdots, (p-1)a\} \pmod{p}.</cmath></center><br><br />
<br />
Clearly none of the <math>ia</math> for <math>1 \le i \le p-1</math> are divisible by <math>p</math>, so it suffices to show that all of the elements in <math>a \cdot S</math> are distinct. Suppose that <math>ai \equiv aj \pmod{p}</math> for <math>i \neq j</math>. Since <math>\text{gcd}\, (a,p) = 1</math>, by the cancellation rule, that reduces to <math>i \equiv j \pmod{p}</math>, which is a contradiction. <br />
<br />
Thus, <math>\mod{p}</math>, we have that the product of the elements of <math>S</math> is <br />
<br />
<center><cmath>1a \cdot 2a \cdots (p-1)a \equiv 1 \cdot 2 \cdots (p-1) \pmod{p}.</cmath></center> <br><br />
<br />
Cancelling the factors <math>1, 2, 3, \ldots, p-1</math> from both sides, we are left with the statement <math>a^{p-1} \equiv 1 \pmod{p}</math>.<br><br />
<br />
A similar version can be used to prove [[Euler's Totient Theorem]], if we let <math>S = \{\text{natural numbers relatively prime to and less than}\ n\}</math>.<br />
<br />
=== Proof 3 (Combinatorics) ===<br />
<center><asy> <br />
real r = 0.3, row1 = 3.5, row2 = 0, row3 = -3.5;<br />
void necklace(pair k, pen colors[]){<br />
draw(shift(k)*unitcircle); <br />
for(int i = 0; i < colors.length; ++i){<br />
pair p = k+expi(pi/2+2*pi*i/colors.length);<br />
fill(Circle(p,r),colors[i]);<br />
draw(Circle(p,r));<br />
}<br />
}<br />
<br />
pen BEADS1[] = {red,red,red},BEADS2[] = {blue,blue,blue},BEADS3[] = {red,red,blue},BEADS4[] = {blue,red,red},BEADS5[] = {red,blue,red},BEADS6[] = {blue,blue,red},BEADS7[] = {red,blue,blue},BEADS8[] = {blue,red,blue};<br />
necklace((-1.5,row1),BEADS1);necklace((1.5,row1),BEADS2);necklace((-2.5,row2),BEADS3);necklace((0,row2),BEADS4);necklace((2.5,row2),BEADS5);necklace((-2.5,row3),BEADS6);necklace((0,row3),BEADS7);necklace((2.5,row3),BEADS8);<br />
</asy><br> An illustration of the case <math>p=3,a=2</math>.<br></center><br />
<br />
Consider a necklace with <math>p</math> beads, each bead of which can be colored in <math>a</math> different ways. There are <math>a^p</math> ways to pick the colors of the beads. <math>a</math> of these are necklaces that consists of beads of the same color. Of the remaining necklaces, for each necklace, there are exactly <math>p-1</math> more necklaces that are rotationally equivalent to this necklace. It follows that <math>a^p-a</math> must be divisible by <math>p</math>. Written in another way, <math>a^p \equiv a \pmod{p}</math>.<br />
<br />
=== Proof 4 (Geometry) ===<br />
<center><asy><br />
void match(int i, int j){ <br />
draw(shift((i,j))*unitsquare,linewidth(1));<br />
draw(shift((j,i))*unitsquare,linewidth(1));<br />
draw((i+0.5,j+0.5)--(j+0.5,i+0.5),linewidth(2));<br />
}<br />
int n = 6;<br />
for(int i = 0; i < n; ++i){<br />
for(int j = 0; j < n; ++j)<br />
draw(shift((i,j))*unitsquare, linewidth(0.5));<br />
}<br />
draw((0,0)--(n,n),red+linewidth(2)); match(2,4); match(0,3);<br />
</asy>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<asy><br />
import three; currentprojection = perspective(3,-2,4);<br />
void match(int i, int j, int k){ <br />
draw(shift((i,j,k))*box((0,0,0),(1,1,1)),linewidth(1));<br />
draw(shift((k,i,j))*box((0,0,0),(1,1,1)),linewidth(1));<br />
draw(shift((j,k,i))*box((0,0,0),(1,1,1)),linewidth(1));<br />
draw((i+0.5,j+0.5,k+0.5)--(j+0.5,k+0.5,i+0.5)--(k+0.5,i+0.5,j+0.5)--cycle,linewidth(2));<br />
}<br />
int n = 4;<br />
for(int i = 0; i < n; ++i){<br />
for(int j = 0; j < n; ++j)<br />
for(int k = 0; k < n; ++k)<br />
draw(shift((i,j,k))*box((0,0,0),(1,1,1)), linewidth(0.5));<br />
}<br />
draw((0,0,0)--(n,n,n),red+linewidth(2));match(2,3,1); </asy>For <math>p=2,3</math> and <math>a=6,4</math>, respectively.</center><br />
We imbed a [[hypercube]] of side length <math>a</math> in <math>\mathbb{R}^p</math> (the <math>p</math>-th dimensional [[Euclidean space]]), such that the vertices of the hypercube are at <math>(\pm a/2,\pm a/2, \ldots, \pm a/2)</math>. A hypercube is essentially a cube, generalized to higher dimensions. This hypercube consists of <math>a^p</math> separate unit hypercubes, with centers consisting of the points <br />
<br />
<center><cmath>P(x_1, x_2, \ldots, x_n) = \left(a + \frac 12 - x_1, a + \frac 12 - x_2, \ldots, a + \frac 12 - x_p\right),</cmath></center><br><br />
<br />
where each <math>x_i</math> is an integer from <math>1</math> to <math>a</math>. Besides the <math>a</math> centers of the unit hypercubes in the main diagonal (from <math>(-a/2, -a/2, \ldots, -a/2)</math> to <math>(a/2, a/2, \ldots, a/2)</math>), the transformation carrying <br />
<br />
<cmath>P(x_1, x_2, \ldots, x_n) \mapsto P(x_2, x_3, \ldots, x_n, x_1)</cmath><br><br />
<br />
maps one unit hypercube to a distinct hypercube. Much like the combinatorial proof, this splits the non-main diagonal unit hypercubes into groups of size <math>p</math>, from which it follows that <math>a^p \equiv a \pmod{p}</math>. Thus, we have another way to visualize the above combinatorial proof, by imagining the described transformation to be, in a sense, a rotation about the main diagonal of the hypercube.<br />
<br />
== Problems ==<br />
=== Introductory ===<br />
* Compute some examples, for example find <math>3^{31} \pmod{7}, 29^{25} \pmod{11}</math>, and <math>128^{129} \pmod{17}</math>, and check your answers by calculator where possible.<br />
<br />
* Let <math>k = 2008^2 + 2^{2008}</math>. What is the units digit of <math>k^2 + 2^k</math>? ([[2008 AMC 12A Problems/Problem 15]])<br />
<br />
* Find <math>2^{20} + 3^{30} + 4^{40} + 5^{50} + 6^{60}</math> mod <math>7</math>. ([http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=207352162&t=304326 Discussion]).<br />
<br />
=== Intermediate ===<br />
* One of Euler's conjectures was disproved in the 1960s by three American mathematicians when they showed there was a positive integer such that <math>133^5+110^5+84^5+27^5=n^5</math>. Find the value of <math>{n}</math>. ([[1989 AIME Problems/Problem 9|1989 AIME, #9]])<br><br><br />
<br />
*If <math>f(x) = x^{x^{x^x}}</math>, find the last two digits of <math>f(17) + f(18) + f(19) + f(20)</math>. ([https://pumac.princeton.edu/info/archives/pumac-2008/ 2008 PUMaC, NT A#5])<br />
<br />
=== Advanced ===<br />
*Is it true that if <math>p</math> is a prime number, and <math>k</math> is an integer <math>2 \le k \le p</math>, then the sum of the products of each <math>k</math>-element subset of <math>\{1, 2, \ldots, p\}</math> will be divisible by <math>p</math>? <br><br><br />
<br />
== Hints/Solutions ==<br />
Introductory: <br />
* Hint: For the first example, we have <math>3^6 \equiv 1 \pmod{7}</math> by FLT (Fermat's Little Theorem). It follows that <math>3^{31} = 3 \cdot 3^{30} = 3 \cdot \left(3^{6}\right)^5 \equiv 3 \cdot 1^5 \equiv 3 \pmod{7}</math>.<br />
<br />
Intermediate:<br />
* Solution (1989 AIME, 9) To solve this problem, it would be nice to know some information about the remainders <math>n</math> can have after division by certain numbers. By Fermat's Little Theorem, we know <math>{n^{5}}</math> is congruent to <math>n</math> [[modulo]] 5. Hence,<br><br />
<center><math>3 + 0 + 4 + 7 \equiv n\pmod{5}</math></center><br />
<center><math>4 \equiv n\pmod{5}</math></center><br />
<br><br><br />
:Continuing, we examine the equation modulo 3,<br />
<center><math>-1 + 1 + 0 + 0 \equiv n\pmod{3}</math></center><br />
<center><math>0 \equiv n\pmod{3}</math></center><br />
<br />
<br><br><br><br />
:Thus, <math>n</math> is divisible by three and leaves a remainder of four when divided by 5. It's obvious that <math>n>133</math>, so the only possibilities are <math>n = 144</math> or <math>n = 174</math>. It quickly becomes apparent that 174 is much too large, so <math>n</math> must be 144.<br />
<br />
Advanced:<br />
* Hint: try to establish the identity <math>x^{p} - x \equiv x(x-1)(x-2) \cdots (x-(p-1)) \pmod{p}</math>, and then apply [[Vieta's formulas]]. <br />
<br />
== See also ==<br />
* [[Number theory]]<br />
* [[Modular arithmetic]]<br />
* [[Euler's Totient Theorem]]<br />
* [[Order (group theory)]]<br />
<br />
[[Category:Number theory]]<br />
[[Category:Theorems]]</div>Sirhcgninilhttps://artofproblemsolving.com/wiki/index.php?title=2014_USAMO_Problems/Problem_5&diff=1075312014 USAMO Problems/Problem 52019-07-10T15:59:49Z<p>Sirhcgninil: /* Solution */</p>
<hr />
<div>==Problem==<br />
Let <math>ABC</math> be a triangle with orthocenter <math>H</math> and let <math>P</math> be the second intersection of the circumcircle of triangle <math>AHC</math> with the internal bisector of the angle <math>\angle BAC</math>. Let <math>X</math> be the circumcenter of triangle <math>APB</math> and <math>Y</math> the orthocenter of triangle <math>APC</math>. Prove that the length of segment <math>XY</math> is equal to the circumradius of triangle <math>ABC</math>.<br />
<br />
==Solution==<br />
Let <math>O_1</math> be the center of <math>(AHPC)</math>, <math>O</math> be the center of <math>(ABC)</math>. Note that <math>(O_1)</math> is the reflection of <math>(O)</math> across <math>AC</math>, so <math>AO=AO_1</math>. Additionally<br />
<cmath><br />
\angle AYC=180-\angle APC=180-\angle AHC=\angle B<br />
</cmath><br />
so <math>Y</math> lies on <math>(O)</math>. Now since <math>XO,OO_1,XO_1</math> are perpendicular to <math>AB,AC,</math> and their bisector, <math>XOO_1</math> is isosceles with <math>XO=OO_1</math>, and <math>\angle XOO_1=180-\angle A</math>. Also<br />
<cmath><br />
\angle AOY=2\angle ACY=2(90-\angle PAC)=2(90-\frac{A}{2})=180-\angle A = \angle XOO_1<br />
</cmath><br />
But <math>YO=OA</math> as well, and <math>\angle YOX=\angle AOO_1</math>, so <math>\triangle OYX\sim \triangle OAO_1</math>. Thus <math>XY=AO_1=AO</math>.</div>Sirhcgninilhttps://artofproblemsolving.com/wiki/index.php?title=Pi_Day&diff=106811Pi Day2019-06-22T00:47:41Z<p>Sirhcgninil: </p>
<hr />
<div>Pi Day is a holiday celebrating the constant [[pi]]. Pi Day is celebrated on March 14th, that is, 3/14 (in American date format). Also, Albert Einstein's birthday is on 3/14 too. One can celebrate Pi Day by reciting <math>\pi</math>, eating pie, etc. This page was created on Pi Day by someone who should have been studying for AIME but instead created a page on Pi Day.</div>Sirhcgninilhttps://artofproblemsolving.com/wiki/index.php?title=Sorgenfrey_plane&diff=105958Sorgenfrey plane2019-05-26T15:20:13Z<p>Sirhcgninil: </p>
<hr />
<div>The '''Sorgenfrey plane''' <math>\mathbb{R}_l \times \mathbb{R}_l</math> is a useful example in [[topology]]. It is formed by taking the [[Cartesian product]] of the [[lower-limit topology]] on <math>\mathbb{R}</math> with itself. <br />
<br />
Let <math>-\Delta = \{x \times (-x) \,|\, x \in \mathbb{R}_l\}</math> be the ''anti-diagonal''. It is a closed subspace of the Sorgenfrey plane, but it inherits the [[discrete topology]] as a subspace: consider the basis element given by <math>[x,x+1) \times [-x,-x+1)</math>.<br />
<br />
{{image}}<br />
<br />
== Countability axioms ==<br />
The Sorgenfrey plane is [[countability axioms|first-countable]], is separable (has a countably dense subset, namely <math>\mathbb{Q}^2</math>), but not Lindelof, and consequently not second-countable (does not have a countable basis). <br />
<br />
== Separation axioms ==<br />
The Sorgenfrey plane is [[separation axioms|regular]], but not [[normal]]. It is regular because it is the Cartesian product of regular spaces. It is not normal; we can see this because any subset <math>A</math> of <math>-\Delta</math> is a closed subspace of <math>\mathbb{R}_l^2</math>, and it can be shown that there do not exist disjoint open sets about <math>A</math> and <math>-\Delta \setminus A</math> in <math>\mathbb{R}_l^2</math>.<br />
<br />
{{stub}}<br />
<br />
[[Category:Topology]]</div>Sirhcgninilhttps://artofproblemsolving.com/wiki/index.php?title=Trigonometric_identities&diff=105862Trigonometric identities2019-05-19T11:48:03Z<p>Sirhcgninil: </p>
<hr />
<div>'''Trigonometric identities''' are used to manipulate [[trigonometry]] [[equation]]s in certain ways. Here is a list of them:<br />
<br />
== Basic Definitions ==<br />
The six basic trigonometric functions can be defined using a right triangle:<br />
<center>[[Image:righttriangle.png]]</center><br />
<br />
The six trig functions are sine, cosine, tangent, cosecant, secant, and cotangent. They are abbreviated by using the first three letters of their name (except for cosecant which uses <math>\csc</math>). They are defined as follows:<br />
{| class="wikitable"<br />
|+ Basic Definitions<br />
|- <!-- Start of a new row --><br />
| <math>\sin A = \frac ac</math> || <math>\csc A = \frac ca</math> || <math> \cos A = \frac bc</math> || <math>\sec A = \frac cb</math> || <math> \tan A = \frac ab</math> || <math> \cot A = \frac ba</math><br />
|}<br />
<br />
== Even-Odd Identities ==<br />
*<math>\sin (-\theta) = -\sin (\theta) </math><br />
<br />
*<math>\cos (-\theta) = \cos (\theta) </math><br />
<br />
*<math>\tan (-\theta) = -\tan (\theta) </math><br />
<br />
*<math>\sec (-\theta) = \sec (\theta) </math><br />
<br />
*<math>\csc (-\theta) = -\csc (\theta) </math><br />
<br />
*<math>\cot (-\theta) = -\cot (\theta) </math><br />
<br />
===Further Conclusions===<br />
<br />
Based on the above identities, we can also claim that<br />
<br />
*<math>\sin(\cos(-\theta)) = \sin(\cos(\theta))</math><br />
<br />
*<math>\cos(\sin(-\theta)) = \cos(-\sin(\theta)) = \cos(\sin(\theta))</math><br />
<br />
This is only true when <math>\sin(\theta)</math> is in the domain of <math>\cos(\theta)</math>.<br />
<br />
== Reciprocal Relations ==<br />
From the first section, it is easy to see that the following hold:<br />
<br />
*<math> \sin A = \frac 1{\csc A}</math> <br />
<br />
*<math> \cos A = \frac 1{\sec A}</math><br />
<br />
*<math> \tan A = \frac 1{\cot A}</math><br />
<br />
Another useful identity that isn't a reciprocal relation is that <math> \tan A =\frac{\sin A}{\cos A} </math>.<br />
<br />
Note that <math>\sin^{-1} A \neq \csc A</math>; the former refers to the [[inverse trigonometric function]]s.<br />
<br />
== Pythagorean Identities ==<br />
Using the [[Pythagorean Theorem]] on our triangle above, we know that <math>a^2 + b^2 = c^2 </math>. If we divide by <math>c^2 </math> we get <math>\left(\frac{a}{c}\right)^2 + \left(\frac{b}{c}\right)^2 = 1 </math>, which is just <math>\sin^2 A + \cos^2 A =1 </math>. Dividing by <math> a^2 </math> or <math> b^2 </math> instead produces two other similar identities. The Pythagorean Identities are listed below:<br />
<br />
*<math>\sin^2x + \cos^2x = 1</math><br />
*<math>1 + \cot^2x = \csc^2x</math><br />
*<math>\tan^2x + 1 = \sec^2x</math><br />
<br />
(Note that the last two are easily derived by dividing the first by <math>\sin^2x</math> and <math>\cos^2x</math>, respectively.)<br />
<br />
== Angle Addition/Subtraction Identities ==<br />
Once we have formulas for angle addition, angle subtraction is rather easy to derive. For example, we just look at <math> \sin(\alpha+(-\beta))</math> and we can derive the sine angle subtraction formula using the sine angle addition formula.<br />
<br />
*<math> \sin(\alpha \pm \beta) = \sin \alpha\cos \beta \pm\sin \beta \cos \alpha</math><br />
*<math> \cos(\alpha \pm \beta) = \cos \alpha \cos \beta \mp \sin \alpha \sin \beta </math><br />
*<math>\tan(\alpha \pm \beta) = \frac{\tan \alpha \pm \tan \beta}{1\mp\tan \alpha \tan \beta} </math><br />
<br />
We can prove <math> \cos(\alpha + \beta) = \cos \alpha \cos \beta - \sin \alpha \sin \beta </math> easily by using <math> \sin(\alpha + \beta) = \sin \alpha\cos \beta +\sin \beta \cos \alpha</math> and <math>\sin(x)=\cos(90-x)</math>.<br />
<br />
<math>\cos (\alpha + \beta)</math><br />
<br />
<math> = \sin((90 -\alpha) - \beta) </math><math>= \sin (90- \alpha) \cos (\beta) - \sin ( \beta) \cos (90- \alpha) </math><br />
<br />
<math>=\cos \alpha \cos \beta - \sin \beta \sin \alpha </math><br />
<br />
== Double Angle Identities ==<br />
Double angle identities are easily derived from the angle addition formulas by just letting <math> \alpha = \beta </math>. Doing so yields:<br />
<br />
<cmath>\begin{eqnarray*}<br />
\sin 2\alpha &=& 2\sin \alpha \cos \alpha\\<br />
\cos 2\alpha &=& \cos^2 \alpha - \sin^2 \alpha\\<br />
&=& 2\cos^2 \alpha - 1\\<br />
&=& 1-2\sin^2 \alpha\\<br />
\tan 2\alpha &=& \frac{2\tan \alpha}{1-\tan^2\alpha} \end{eqnarray*}</cmath><br />
<br />
=Further Conclusions=<br />
<br />
We can see from the above that<br />
<br />
*<math>\csc(2a) = \frac{\csc(a)\sec(a)}{2}</math><br />
*<math>\sec(2a) = \frac{1}{2\cos^2(a) - 1} = \frac{1}{\cos^2(a) - \sin^2(a)} = \frac{1}{1 - 2\sin^2(a)}</math><br />
*<math>\cot(2a) = \frac{1 - \tan^2(a)}{2\tan(a)}</math><br />
<br />
== Half Angle Identities ==<br />
Using the double angle identities, we can derive half angle identities. The double angle formula for cosine tells us <math>\cos 2\alpha = 2\cos^2 \alpha - 1 </math>. Solving for <math>\cos \alpha </math> we get <math>\cos \alpha =\pm \sqrt{\frac{1 + \cos 2\alpha}2}</math> where we look at the quadrant of <math>\alpha </math> to decide if it's positive or negative. Likewise, we can use the fact that <math>\cos 2\alpha = 1 - 2\sin^2 \alpha </math> to find a half angle identity for sine. Then, to find a half angle identity for tangent, we just use the fact that <math>\tan \frac x2 =\frac{\sin \frac x2}{\cos \frac x2} </math> and plug in the half angle identities for sine and cosine.<br />
<br />
To summarize:<br />
<br />
*<math> \sin \frac{\theta}2 = \pm \sqrt{\frac{1-\cos \theta}2} </math><br />
*<math> \cos \frac{\theta}2 = \pm \sqrt{\frac{1+\cos \theta}2} </math><br />
*<math> \tan \frac{\theta}2 = \pm \sqrt{\frac{1-\cos \theta}{1+\cos \theta}}=\frac{\sin \theta}{1+\cos\theta}=\frac{1-\cos\theta}{\sin \theta} </math><br />
<br />
== Prosthaphaeresis Identities ==<br />
(Otherwise known as sum-to-product identities)<br />
<br />
* <math>\displaystyle{\sin \theta + \sin \gamma = 2 \sin \frac{\theta + \gamma}2 \cos \frac{\theta - \gamma}2}</math><br />
* <math>\displaystyle{\sin \theta - \sin \gamma = 2 \sin \frac{\theta - \gamma}2 \cos \frac{\theta + \gamma}2}</math><br />
* <math>\displaystyle{\cos \theta + \cos \gamma = 2 \cos \frac{\theta+\gamma}2 \cos \frac{\theta-\gamma}2}</math><br />
* <math>\displaystyle{\cos \theta - \cos \gamma = -2 \sin \frac{\theta+\gamma}2 \sin \frac{\theta-\gamma}2}</math><br />
<br />
== Law of Sines ==<br />
{{main|Law of Sines}}<br />
The extended [[Law of Sines]] states<br />
<br />
*<math>\frac a{\sin A} = \frac b{\sin B} = \frac c{\sin C} = 2R.</math><br />
<br />
== Law of Cosines ==<br />
{{main|Law of Cosines}}<br />
The [[Law of Cosines]] states <br />
<br />
*<math>a^2 = b^2 + c^2 - 2bc\cos A. </math><br />
<br />
== Law of Tangents ==<br />
{{main|Law of Tangents}}<br />
The [[Law of Tangents]] states that if <math>A</math> and <math>B</math> are angles in a triangle opposite sides <math>a</math> and <math>b</math> respectively, then<br />
<br />
<math> \frac{\tan{\left(\frac{A-B}{2}\right)}}{\tan{\left(\frac{A+B}{2}\right)}}=\frac{a-b}{a+b} . </math><br />
<br />
A further extension of the [[Law of Tangents]] states that if <math>A</math>, <math>B</math>, and <math>C</math> are angles in a triangle, then<br />
<math>\tan(A)\cdot\tan(B)\cdot\tan(C)=\tan(A)+\tan(B)+\tan(C)</math><br />
<br />
== Other Identities ==<br />
*<math>\sin(90-\theta) = \cos(\theta)</math><br />
*<math>\cos(90-\theta)=\sin(\theta)</math><br />
*<math>\tan(90-\theta)=\cot(\theta)</math><br />
*<math>\sin(180-\theta) = \sin(\theta)</math><br />
*<math>\cos(180-\theta) = -\cos(\theta)</math><br />
*<math>\tan(180-\theta) = -\tan(\theta)</math><br />
*<math>e^{i\theta} = \cos \theta + i\sin \theta</math> (This is also written as <math>\text{cis }\theta</math>)<br />
*<math>|1-e^{i\theta}|=2\sin\frac{\theta}{2}</math><br />
*<math>\left(\tan\theta + \sec\theta\right)^2 = \frac{1 + \sin\theta}{1 - \sin\theta}</math><br />
*<math>\sin(\theta) = \cos(\theta)\tan(\theta)</math><br />
*<math>\cos(\theta) = \frac{\sin(\theta)}{\tan(\theta)}</math><br />
*<math>\sec(\theta) = \frac{\tan(\theta)}{\sin(\theta)}</math><br />
*<math>\sin^2(\theta) + \cos^2(\theta) + \tan^2(\theta) = \sec^2(\theta)</math><br />
*<math>\sin^2(\theta) + \cos^2(\theta) + \cot^2(\theta) = \csc^2(\theta)</math><br />
<br />
The two identities right above here were based on identities others posted on this site with a substitution.<br />
<br />
*<math>\cos(2\theta) = (\cos(\theta) + \sin(\theta))(\cos(\theta) - \sin(\theta))</math><br />
<br />
==See also==<br />
* [[Trigonometry]]<br />
* [[Trigonometric substitution]]<br />
<br />
==External Links==<br />
[http://www.sosmath.com/trig/Trig5/trig5/trig5.html Trigonometric Identities]<br />
<br />
[[Category:Trigonometry]]</div>Sirhcgninilhttps://artofproblemsolving.com/wiki/index.php?title=Fibonacci_sequence&diff=105786Fibonacci sequence2019-05-13T14:26:53Z<p>Sirhcgninil: </p>
<hr />
<div>The '''Fibonacci sequence''' is a [[sequence]] of [[integer]]s in which the first and second terms are both equal to 1 and each subsequent term is the sum of the two preceding it. The first few terms are <math>1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...</math>.<br />
<br />
==Recursion==<br />
The Fibonacci sequence can be written [[recursion|recursively]] as <math>F_1 = F_2 = 1</math> and <math>F_n=F_{n-1}+F_{n-2}</math> for <math>n \geq 3</math>. This is the simplest nontrivial example of a [[linear recursion]] with constant coefficients. There is also an explicit formula [[#Binet's formula|below]].<br />
<br />
Readers should be wary: some authors give the Fibonacci sequence with the [[initial condition]]s <math>F_0 = F_1 = 1</math> (or equivalently <math>F_1 = 1, F_2 = 2</math>). This change in [[indexing of a sequence | indexing]] does not affect the actual numbers in the sequence, but it does change which member of the sequence is referred to by the symbol <math>F_n</math> and so also changes the appearance of certain [[identity | identities]] involving the Fibonacci numbers. <br />
<br />
== Running Backwards ==<br />
As with many linear recursions, we can run the Fibonacci sequence backwards by solving its recursion relation for the term of smallest index, in this case <math>F_{n - 2} = F_{n} - F_{n - 1}</math>. This allows us to compute, for example, that <math>F_0 = F_2 - F_1 = 0</math>, <math>F_{-1} = 1</math>, <math>F_{-2} = -2</math>, and so on. Because these preceding terms are uniquely defined by the recursion, one frequently sees the definition of the Fibonacci sequence given in the form <math>F_0 = 0</math>, <math>F_1 = 1</math> and <math>F_n = F_{n - 1} + F_{n - 2}</math> for <math>n \geq 2</math>. In general, one can show that <math>F_n = (-1)^{n+1}F_{-n}</math>.<br />
<br />
== <math>\varphi</math> and Binet's Formula==<br />
{{main|Binet's formula}}<br />
<br />
The ratios <math>\frac{1}{1}</math>, <math>\frac{2}{1}</math>, <math>\frac{3}{2}</math>, <math>\frac{5}{3}</math>, <math>\frac{8}{5}</math>, ..., between successive terms of the sequence tend towards the limit <math>\frac{1 + \sqrt{5}}{2}</math>, a constant often denoted <math>\varphi</math> (the Greek letter [[phi]], also written <math>\phi</math>). <math>\varphi</math> is a solution of the quadratic equation <math>x^2-x-1=0</math>. The other root is <math>-\varphi^{-1} = \frac{1-\sqrt{5}}{2}</math>. One possible explanation for this fact is that the Fibonacci numbers are given explicitly by Binet's formula. It is <br />
<math>F_n = \frac{\varphi^n - (-\varphi)^{-n}}{\sqrt{5}}</math>.<br />
(Note that this formula is valid for all integers <math>n</math>.)<br />
It is so named because it was derived by mathematician Jacques Philippe Marie Binet, though it was already known by Abraham de Moivre.<br />
<br />
== Identities ==<br />
The most important identity regarding the Fibonacci sequence is its recursive definition, <math>F_{n+1} = F_n + F_{n-1}</math>. The following identities involving the Fibonacci numbers can be proved by [[induction]].<br />
<br />
*<math>F_0 + F_1 + \cdots + F_{n} = F_{n+2} - 1</math><br />
*<math>F_0 - F_1 + F_2 - \cdots - F_{2n-1} + F_{2n} = F_{2n-1} - 1</math><br />
*<math>F_0^2 + F_1^2 + F_2^2 + \cdots + F_n^2 = F_n \cdot F_{n+1}</math><br />
*<math>F_{n-1}\cdot F_{n+1} = F_{n}^2 + (-1)^n</math><br />
*<math>F_{m+n+1} = F_{m+1} \cdot F_{n+1} + F_{m} \cdot F_n</math><br />
<br />
==Problems==<br />
=== Introductory ===<br />
# The Fibonacci sequence <math>1,1,2,3,5,8,13,21,\ldots </math> starts with two 1s, and each term afterwards is the sum of its two predecessors. Which one of the ten [[digit]]s is the last to appear in the units position of a number in the Fibonacci sequence?<br><br><math> \mathrm{(A) \ 0 } \qquad \mathrm{(B) \ 4 } \qquad \mathrm{(C) \ 6 } \qquad \mathrm{(D) \ 7 } \qquad \mathrm{(E) \ 9 } </math><div style="text-align:right">([[2000 AMC 12 Problems/Problem 4|2000 AMC 12, Problem 4]])</div><br />
# A colony has <math>1</math> rabbit. A rabbit produces one offspring every month. An offspring rabbit takes one month to grow up. Find a formula for the number of rabbits (including offspring) in the <math>n</math>th month.<br />
## How about if the colony starts with <math>a</math> rabbits and <math>b</math> offspring? <br />
## Use this result to prove the identity <math>F_{m+n+1} = F_{m+1} \cdot F_{n+1} + F_{m} \cdot F_n</math>.<br />
# Find <math>\gcd(F_n,F_{n+1})</math>.<br />
# Prove the above [[#Identities|identites]].<br />
<br />
=== Intermediate ===<br />
# Seven line segments, with lengths no greater than 10 inches, and no shorter than 1 inch, are given. Show that one can choose three of them to represent the sides of a triangle. <div style="text-align:right">(Manhattan Mathematical Olympiad 2004)</div><br />
# Except for the first two terms, each term of the sequence <math>1000, x, 1000 - x,\ldots</math> is obtained by subtracting the preceding term from the one before that. The last term of the sequence is the first [[negative]] term encounted. What positive integer <math>x</math> produces a sequence of maximum length? <div style="text-align:right">([[1998 AIME Problems/Problem 8|1998 AIME, Problem 8]])</div><br />
# A fair coin is to be tossed <math>10_{}^{}</math> times. Let <math>\frac ij^{}_{}</math>, in lowest terms, be the [[probability]] that heads never occur on consecutive tosses. Find <math>i+j_{}^{}</math>. <div style="text-align:right">([[1990 AIME Problems/Problem 9|1990 AIME, Problem 9]])</div><br />
#Find <math>a</math> if <math>a</math> and <math>b</math> are [[integer]]s such that <math>x^2 - x - 1</math> is a factor of <math>ax^{17} + bx^{16} + 1</math>. <div style="text-align:right">([[1988 AIME Problems/Problem 13|1988 AIME, Problem 13]])</div><br />
<br />
=== Olympiad ===<br />
# Determine the maximum value of <math>m^2 + n^2 </math>, where <math>m </math> and <math>n </math> are integers satisfying <math> m, n \in \{ 1,2, \ldots , 1981 \} </math> and <math>( n^2 - mn - m^2 )^2 = 1 </math>. <div style="text-align:right">([[1981 IMO Problems/Problem 3|1981 IMO, Problem 3]])</div><br />
<br />
==See also==<br />
* [[Combinatorics]]<br />
* [[Lucas Numbers]]<br />
<br />
==External Links==<br />
* [http://www.scriptspedia.org/Fibonacci_Numbers Fibonacci Algorithm implementation in C++, Java and Javascript]<br />
[[Category:Combinatorics]]</div>Sirhcgninilhttps://artofproblemsolving.com/wiki/index.php?title=1981_IMO_Problems/Problem_3&diff=1057851981 IMO Problems/Problem 32019-05-13T14:23:54Z<p>Sirhcgninil: </p>
<hr />
<div>== Problem ==<br />
<br />
Determine the maximum value of <math>m^2 + n^2 </math>, where <math>m </math> and <math>n </math> are integers satisfying <math> m, n \in \{ 1,2, \ldots , 1981 \} </math> and <math>( n^2 - mn - m^2 )^2 = 1 </math>.<br />
<br />
== Solution ==<br />
<br />
We first observe that since <math>\gcd(m,n)=1 </math>, <math>m</math> and <math>n</math> are [[relatively prime]]. In addition, we note that <math>n \ge m</math>, since if we had <math>n < m</math>, then <math>n^2 -nm -m^2 = n(n-m) - m^2 </math> would be the sum of two negative integers and therefore less than <math>-1</math>. We now observe<br />
<br />
<cmath><br />
(m+k)^2 -(m+k)m - m^2 = -(m^2 - km - k^2)<br />
</cmath>,<br />
<br />
i.e., <math>(m,n) = (a,b) </math> is a solution [[iff]]. <math>(b, a+b) </math> is also a solution. Therefore, for a solution <math>(m, n)</math>, we can perform the [[Euclidean algorithm]] to reduce it eventually to a solution <math>(1,n) </math>. It is easy to verify that if <math>n </math> is a positive integer, it must be either 2 or 1. Thus by trivial induction, all the positive integer solutions are of the form <math>(F_{n}, F_{n+1})</math>, where the <math>F_i</math> are the [[Fibonacci numbers]]. Simple calculation reveals <math>987</math> and <math>1597</math> to be the greatest Fibonacci numbers less than <math>1981</math>, giving <math>987^2 + 1597^2=3524578</math> as the maximal value.<br />
<br />
<br />
{{alternate solutions}}<br />
<br />
{{IMO box|num-b=2|num-a=4|year=1981}}<br />
<br />
[[Category:Olympiad Number Theory Problems]]</div>Sirhcgninilhttps://artofproblemsolving.com/wiki/index.php?title=Fibonacci_sequence&diff=105784Fibonacci sequence2019-05-13T14:13:15Z<p>Sirhcgninil: </p>
<hr />
<div>The '''Fibonacci sequence''' is a [[sequence]] of [[integer]]s in which the first and second terms are both equal to 1 and each subsequent term is the sum of the two preceding it. The first few terms are <math>1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...</math>.<br />
<br />
==Recursion==<br />
The Fibonacci sequence can be written [[recursion|recursively]] as <math>F_1 = F_2 = 1</math> and <math>F_n=F_{n-1}+F_{n-2}</math> for <math>n \geq 3</math>. This is the simplest nontrivial example of a [[linear recursion]] with constant coefficients. There is also an explicit formula [[#Binet's formula|below]].<br />
<br />
Readers should be wary: some authors give the Fibonacci sequence with the [[initial condition]]s <math>F_0 = F_1 = 1</math> (or equivalently <math>F_1 = 1, F_2 = 2</math>). This change in [[indexing of a sequence | indexing]] does not affect the actual numbers in the sequence, but it does change which member of the sequence is referred to by the symbol <math>F_n</math> and so also changes the appearance of certain [[identity | identities]] involving the Fibonacci numbers. <br />
<br />
== Running Backwards ==<br />
As with many linear recursions, we can run the Fibonacci sequence backwards by solving its recursion relation for the term of smallest index, in this case <math>F_{n - 2} = F_{n} - F_{n - 1}</math>. This allows us to compute, for example, that <math>F_0 = F_2 - F_1 = 0</math>, <math>F_{-1} = 1</math>, <math>F_{-2} = -2</math>, and so on. Because these preceding terms are uniquely defined by the recursion, one frequently sees the definition of the Fibonacci sequence given in the form <math>F_0 = 0</math>, <math>F_1 = 1</math> and <math>F_n = F_{n - 1} + F_{n - 2}</math> for <math>n \geq 2</math>. In general, one can show that <math>F_n = (-1)^{n+1}F_{-n}</math>.<br />
<br />
== <math>\varphi</math> and Binet's Formula==<br />
{{main|Binet's formula}}<br />
<br />
The ratios <math>\frac{1}{1}</math>, <math>\frac{2}{1}</math>, <math>\frac{3}{2}</math>, <math>\frac{5}{3}</math>, <math>\frac{8}{5}</math>, ..., between successive terms of the sequence tend towards the limit <math>\frac{1 + \sqrt{5}}{2}</math>, a constant often denoted <math>\varphi</math> (the Greek letter [[phi]], also written <math>\phi</math>). <math>\varphi</math> is a solution of the quadratic equation <math>x^2-x-1=0</math>. The other root is <math>-\varphi^{-1} = \frac{1-\sqrt{5}}{2}</math>. One possible explanation for this fact is that the Fibonacci numbers are given explicitly by Binet's formula. It is <br />
<math>F_n = \frac{\varphi^n - (-\varphi)^{-n}}{\sqrt{5}}</math>.<br />
(Note that this formula is valid for all integers <math>n</math>.)<br />
It is so named because it was derived by mathematician Jacques Philippe Marie Binet, though it was already known by Abraham de Moivre.<br />
<br />
== Identities ==<br />
The most important identity regarding the Fibonacci sequence is its recursive definition, <math>F_{n+1} = F_n + F_{n-1}</math>. The following identities involving the Fibonacci numbers can be proved by [[induction]].<br />
<br />
*<math>F_0 + F_1 + \cdots + F_{n} = F_{n+2} - 1</math><br />
*<math>F_0 - F_1 + F_2 - \cdots - F_{2n-1} + F_{2n} = F_{2n-1} - 1</math><br />
*<math>F_0^2 + F_1^2 + F_2^2 + \cdots + F_n^2 = F_n \cdot F_{n+1}</math><br />
*<math>F_{n-1}\cdot F_{n+1} = F_{n}^2 + (-1)^n</math><br />
*<math>F_{m+n+1} = F_{m+1} \cdot F_{n+1} + F_{m} \cdot F_n</math><br />
<br />
==Problems==<br />
=== Introductory ===<br />
# The Fibonacci sequence <math>1,1,2,3,5,8,13,21,\ldots </math> starts with two 1s, and each term afterwards is the sum of its two predecessors. Which one of the ten [[digit]]s is the last to appear in the units position of a number in the Fibonacci sequence?<br><br><math> \mathrm{(A) \ 0 } \qquad \mathrm{(B) \ 4 } \qquad \mathrm{(C) \ 6 } \qquad \mathrm{(D) \ 7 } \qquad \mathrm{(E) \ 9 } </math><div style="text-align:right">([[2000 AMC 12 Problems/Problem 4|2000 AMC 12, Problem 4]])</div><br />
# A colony has <math>1</math> rabbit. A rabbit produces one offspring every month. An offspring rabbit takes one month to grow up. Find a formula for the number of rabbits (including offspring) in the <math>n</math>th month.<br />
## How about if the colony starts with <math>a</math> rabbits and <math>b</math> offspring? <br />
## Use this result to prove the identity <math>F_{m+n+1} = F_{m+1} \cdot F_{n+1} + F_{m} \cdot F_n</math>.<br />
# Find <math>\gcd(F_n,F_{n+1})</math>.<br />
# Prove the above [[#Identities|identites]].<br />
<br />
=== Intermediate ===<br />
# Seven line segments, with lengths no greater than 10 inches, and no shorter than 1 inch, are given. Show that one can choose three of them to represent the sides of a triangle. <div style="text-align:right">(Manhattan Mathematical Olympiad 2004)</div><br />
# Except for the first two terms, each term of the sequence <math>1000, x, 1000 - x,\ldots</math> is obtained by subtracting the preceding term from the one before that. The last term of the sequence is the first [[negative]] term encounted. What positive integer <math>x</math> produces a sequence of maximum length? <div style="text-align:right">([[1998 AIME Problems/Problem 8|1998 AIME, Problem 8]])</div><br />
# A fair coin is to be tossed <math>10_{}^{}</math> times. Let <math>i/j^{}_{}</math>, in lowest terms, be the [[probability]] that heads never occur on consecutive tosses. Find <math>i+j_{}^{}</math>. <div style="text-align:right">([[1990 AIME Problems/Problem 9|1990 AIME, Problem 9]])</div><br />
#Find <math>a</math> if <math>a</math> and <math>b</math> are [[integer]]s such that <math>x^2 - x - 1</math> is a factor of <math>ax^{17} + bx^{16} + 1</math>. <div style="text-align:right">([[1988 AIME Problems/Problem 13|1988 AIME, Problem 13]])</div><br />
<br />
=== Olympiad ===<br />
# Determine the maximum value of <math>m^2 + n^2 </math>, where <math>m </math> and <math>n </math> are integers satisfying <math> m, n \in \{ 1,2, \ldots , 1981 \} </math> and <math>( n^2 - mn - m^2 )^2 = 1 </math>. <div style="text-align:right">([[1981 IMO Problems/Problem 3|1981 IMO, Problem 3]])</div><br />
<br />
==See also==<br />
* [[Combinatorics]]<br />
* [[Lucas Numbers]]<br />
<br />
==External Links==<br />
* [http://www.scriptspedia.org/Fibonacci_Numbers Fibonacci Algorithm implementation in C++, Java and Javascript]<br />
[[Category:Combinatorics]]</div>Sirhcgninilhttps://artofproblemsolving.com/wiki/index.php?title=Trigonometric_identities&diff=105523Trigonometric identities2019-04-28T12:52:53Z<p>Sirhcgninil: </p>
<hr />
<div>'''Trigonometric identities''' are used to manipulate [[trigonometry]] [[equation]]s in certain ways. Here is a list of them:<br />
<br />
== Basic Definitions ==<br />
The six basic trigonometric functions can be defined using a right triangle:<br />
<center>[[Image:righttriangle.png]]</center><br />
<br />
The six trig functions are sine, cosine, tangent, cosecant, secant, and cotangent. They are abbreviated by using the first three letters of their name (except for cosecant which uses <math>\csc</math>). They are defined as follows:<br />
{| class="wikitable"<br />
|+ Basic Definitions<br />
|- <!-- Start of a new row --><br />
| <math>\sin A = \frac ac</math> || <math>\csc A = \frac ca</math> || <math> \cos A = \frac bc</math> || <math>\sec A = \frac cb</math> || <math> \tan A = \frac ab</math> || <math> \cot A = \frac ba</math><br />
|}<br />
<br />
== Even-Odd Identities ==<br />
*<math>\sin (-\theta) = -\sin (\theta) </math><br />
<br />
*<math>\cos (-\theta) = \cos (\theta) </math><br />
<br />
*<math>\tan (-\theta) = -\tan (\theta) </math><br />
<br />
*<math>\sec (-\theta) = \sec (\theta) </math><br />
<br />
*<math>\csc (-\theta) = -\csc (\theta) </math><br />
<br />
*<math>\cot (-\theta) = -\cot (\theta) </math><br />
<br />
===Further Conclusions===<br />
<br />
Based on the above identities, we can also claim that<br />
<br />
*<math>\sin(\cos(-\theta)) = \sin(\cos(\theta))</math><br />
<br />
*<math>\cos(\sin(-\theta)) = \cos(-\sin(\theta)) = \cos(\sin(\theta))</math><br />
<br />
This is only true when <math>\sin(\theta)</math> is in the domain of <math>\cos(\theta)</math>.<br />
<br />
== Reciprocal Relations ==<br />
From the first section, it is easy to see that the following hold:<br />
<br />
*<math> \sin A = \frac 1{\csc A}</math> <br />
<br />
*<math> \cos A = \frac 1{\sec A}</math><br />
<br />
*<math> \tan A = \frac 1{\cot A}</math><br />
<br />
Another useful identity that isn't a reciprocal relation is that <math> \tan A =\frac{\sin A}{\cos A} </math>.<br />
<br />
Note that <math>\sin^{-1} A \neq \csc A</math>; the former refers to the [[inverse trigonometric function]]s.<br />
<br />
== Pythagorean Identities ==<br />
Using the [[Pythagorean Theorem]] on our triangle above, we know that <math>a^2 + b^2 = c^2 </math>. If we divide by <math>c^2 </math> we get <math>\left(\frac{a}{c}\right)^2 + \left(\frac{b}{c}\right)^2 = 1 </math>, which is just <math>\sin^2 A + \cos^2 A =1 </math>. Dividing by <math> a^2 </math> or <math> b^2 </math> instead produces two other similar identities. The Pythagorean Identities are listed below:<br />
<br />
*<math>\sin^2x + \cos^2x = 1</math><br />
*<math>1 + \cot^2x = \csc^2x</math><br />
*<math>\tan^2x + 1 = \sec^2x</math><br />
<br />
(Note that the last two are easily derived by dividing the first by <math>\sin^2x</math> and <math>\cos^2x</math>, respectively.)<br />
<br />
== Angle Addition/Subtraction Identities ==<br />
Once we have formulas for angle addition, angle subtraction is rather easy to derive. For example, we just look at <math> \sin(\alpha+(-\beta))</math> and we can derive the sine angle subtraction formula using the sine angle addition formula.<br />
<br />
*<math> \sin(\alpha \pm \beta) = \sin \alpha\cos \beta \pm\sin \beta \cos \alpha</math><br />
*<math> \cos(\alpha \pm \beta) = \cos \alpha \cos \beta \mp \sin \alpha \sin \beta </math><br />
*<math>\tan(\alpha \pm \beta) = \frac{\tan \alpha \pm \tan \beta}{1\mp\tan \alpha \tan \beta} </math><br />
<br />
We can prove <math> \cos(\alpha + \beta) = \cos \alpha \cos \beta - \sin \alpha \sin \beta </math> easily by using <math> \sin(\alpha + \beta) = \sin \alpha\cos \beta +\sin \beta \cos \alpha</math> and <math>\sin(x)=\cos(90-x)</math>.<br />
<br />
<math>\cos (\alpha + \beta)</math><br />
<br />
<math> = \sin((90 -\alpha) - \beta) </math><math>= \sin (90- \alpha) \cos (\beta) - \sin ( \beta) \cos (90- \alpha) </math><br />
<br />
<math>=\cos \alpha \cos \beta - \sin \beta \sin \alpha </math><br />
<br />
== Double Angle Identities ==<br />
Double angle identities are easily derived from the angle addition formulas by just letting <math> \alpha = \beta </math>. Doing so yields:<br />
<br />
<cmath>\begin{eqnarray*}<br />
\sin 2\alpha &=& 2\sin \alpha \cos \alpha\\<br />
\cos 2\alpha &=& \cos^2 \alpha - \sin^2 \alpha\\<br />
&=& 2\cos^2 \alpha - 1\\<br />
&=& 1-2\sin^2 \alpha\\<br />
\tan 2\alpha &=& \frac{2\tan \alpha}{1-\tan^2\alpha} \end{eqnarray*}</cmath><br />
<br />
=Further Conclusions=<br />
<br />
We can see from the above that<br />
<br />
*<math>\csc(2a) = \frac{\csc(a)\sec(a)}{2}</math><br />
*<math>\sec(2a) = \frac{1}{2\cos^2(a) - 1} = \frac{1}{\cos^2(a) - \sin^2(a)} = \frac{1}{1 - 2\sin^2(a)}</math><br />
*<math>\cot(2a) = \frac{1 - \tan^2(a)}{2\tan(a)}</math><br />
<br />
== Half Angle Identities ==<br />
Using the double angle identities, we can derive half angle identities. The double angle formula for cosine tells us <math>\cos 2\alpha = 2\cos^2 \alpha - 1 </math>. Solving for <math>\cos \alpha </math> we get <math>\cos \alpha =\pm \sqrt{\frac{1 + \cos 2\alpha}2}</math> where we look at the quadrant of <math>\alpha </math> to decide if it's positive or negative. Likewise, we can use the fact that <math>\cos 2\alpha = 1 - 2\sin^2 \alpha </math> to find a half angle identity for sine. Then, to find a half angle identity for tangent, we just use the fact that <math>\tan \frac x2 =\frac{\sin \frac x2}{\cos \frac x2} </math> and plug in the half angle identities for sine and cosine.<br />
<br />
To summarize:<br />
<br />
*<math> \sin \frac{\theta}2 = \pm \sqrt{\frac{1-\cos \theta}2} </math><br />
*<math> \cos \frac{\theta}2 = \pm \sqrt{\frac{1+\cos \theta}2} </math><br />
*<math> \tan \frac{\theta}2 = \pm \sqrt{\frac{1-\cos \theta}{1+\cos \theta}}=\frac{\sin \theta}{1+\cos\theta}=\frac{1-\cos\theta}{\sin \theta} </math><br />
<br />
== Prosthaphaeresis Identities ==<br />
(Otherwise known as sum-to-product identities)<br />
<br />
* <math>\sin \theta \pm \sin \gamma = 2 \sin \frac{\theta\pm \gamma}2 \cos \frac{\theta\mp \gamma}2</math><br />
* <math>\cos \theta + \cos \gamma = 2 \cos \frac{\theta+\gamma}2 \cos \frac{\theta-\gamma}2</math><br />
* <math>\cos \theta - \cos \gamma = -2 \sin \frac{\theta+\gamma}2 \sin \frac{\theta-\gamma}2</math><br />
<br />
== Law of Sines ==<br />
{{main|Law of Sines}}<br />
The extended [[Law of Sines]] states<br />
<br />
*<math>\frac a{\sin A} = \frac b{\sin B} = \frac c{\sin C} = 2R.</math><br />
<br />
== Law of Cosines ==<br />
{{main|Law of Cosines}}<br />
The [[Law of Cosines]] states <br />
<br />
*<math>a^2 = b^2 + c^2 - 2bc\cos A. </math><br />
<br />
== Law of Tangents ==<br />
{{main|Law of Tangents}}<br />
The [[Law of Tangents]] states that if <math>A</math> and <math>B</math> are angles in a triangle opposite sides <math>a</math> and <math>b</math> respectively, then<br />
<br />
<math> \frac{\tan{\left(\frac{A-B}{2}\right)}}{\tan{\left(\frac{A+B}{2}\right)}}=\frac{a-b}{a+b} . </math><br />
<br />
A further extension of the [[Law of Tangents]] states that if <math>A</math>, <math>B</math>, and <math>C</math> are angles in a triangle, then<br />
<math>\tan(A)\cdot\tan(B)\cdot\tan(C)=\tan(A)+\tan(B)+\tan(C)</math><br />
<br />
== Other Identities ==<br />
*<math>\sin(90-\theta) = \cos(\theta)</math><br />
*<math>\cos(90-\theta)=\sin(\theta)</math><br />
*<math>\tan(90-\theta)=\cot(\theta)</math><br />
*<math>\sin(180-\theta) = \sin(\theta)</math><br />
*<math>\cos(180-\theta) = -\cos(\theta)</math><br />
*<math>\tan(180-\theta) = -\tan(\theta)</math><br />
*<math>e^{i\theta} = \cos \theta + i\sin \theta</math> (This is also written as <math>\text{cis }\theta</math>)<br />
*<math>|1-e^{i\theta}|=2\sin\frac{\theta}{2}</math><br />
*<math>\left(\tan\theta + \sec\theta\right)^2 = \frac{1 + \sin\theta}{1 - \sin\theta}</math><br />
*<math>\sin(\theta) = \cos(\theta)\tan(\theta)</math><br />
*<math>\cos(\theta) = \frac{\sin(\theta)}{\tan(\theta)}</math><br />
*<math>\sec(\theta) = \frac{\tan(\theta)}{\sin(\theta)}</math><br />
*<math>\sin^2(\theta) + \cos^2(\theta) + \tan^2(\theta) = \sec^2(\theta)</math><br />
*<math>\sin^2(\theta) + \cos^2(\theta) + \cot^2(\theta) = \csc^2(\theta)</math><br />
<br />
The two identities right above here were based on identities others posted on this site with a substitution.<br />
<br />
*<math>\cos(2\theta) = (\cos(\theta) + \sin(\theta))(\cos(\theta) - \sin(\theta))</math><br />
<br />
==See also==<br />
* [[Trigonometry]]<br />
* [[Trigonometric substitution]]<br />
<br />
==External Links==<br />
[http://www.sosmath.com/trig/Trig5/trig5/trig5.html Trigonometric Identities]<br />
<br />
[[Category:Trigonometry]]</div>Sirhcgninilhttps://artofproblemsolving.com/wiki/index.php?title=Nesbitt%27s_Inequality&diff=105470Nesbitt's Inequality2019-04-23T15:47:38Z<p>Sirhcgninil: </p>
<hr />
<div>'''Nesbitt's [[Inequality]]''' is a theorem which, although rarely cited, has many instructive proofs. It states that for positive <math>a, b, c </math>,<br />
<center><br />
<math><br />
\frac{a}{b+c} + \frac{b}{c+a} + \frac{c}{a+b} \ge \frac{3}{2}<br />
</math>,<br />
</center><br />
with equality when all the variables are equal.<br />
<br />
All of the proofs below generalize to proof the following more general inequality.<br />
<br />
If <math> a_1, \ldots a_n </math> are positive and <math> \sum_{i=1}^{n}a_i = s </math>, then <br />
<center><br />
<math><br />
\sum_{i=1}^{n}\frac{a_i}{s-a_i} \geq \frac{n}{n-1}<br />
</math>,<br />
</center><br />
or equivalently<br />
<center><br />
<math><br />
\sum_{i=1}^{n}\frac{s}{s-a_i} \geq \frac{n^2}{n-1}<br />
</math>,<br />
</center><br />
with equality when all the <math>a_i </math> are equal.<br />
<br />
== Proofs ==<br />
<br />
=== By Rearrangement ===<br />
<br />
Note that <math>a,b,c </math> and <math> \frac{1}{b+c} = \frac{1}{a+b+c -a}</math>, <math> \frac{1}{c+a} = \frac{1}{a+b+c -b} </math>, <math> \frac{1}{a+b} = \frac{1}{a+b+c -c} </math> are sorted in the same order. Then by the [[rearrangement inequality]],<br />
<center><br />
<math><br />
2 \left( \frac{a}{b+c} + \frac{b}{c+a} + \frac{c}{a+b} \right) \ge \frac{b}{b+c} + \frac{c}{b+c} + \frac{c}{c+a} + \frac{a}{c+a} + \frac{a}{a+b} + \frac{b}{a+b} = 3<br />
</math>.<br />
</center><br />
For equality to occur, since we changed <math>{} a \cdot \frac{1}{b+c} + b \cdot \frac{1}{c+a} </math> to <math> b \cdot \frac{1}{b+c} + a \cdot \frac{1}{c+a} </math>, we must have <math>a=b </math>, so by symmetry, all the variables must be equal.<br />
<br />
=== By Cauchy ===<br />
<br />
By the [[Cauchy-Schwarz Inequality]], we have<br />
<center><br />
<math><br />
[(b+c) + (c+a) + (a+b)]\left( \frac{1}{b+c} + \frac{1}{c+a} + \frac{1}{a+b} \right) \geq 9<br />
</math>,<br />
</center><br />
or<br />
<center><br />
<math><br />
2\left( \frac{a+b+c}{b+c} + \frac{a+b+c}{c+a} + \frac{a+b+c}{a+b} \right) \geq 9<br />
</math>,<br />
</center><br />
as desired. Equality occurs when <math>(b+c)^2 = (c+a)^2 = (a+b)^2 </math>, i.e., when <math>a=b=c </math>.<br />
<br />
We also present three closely related variations of this proof, which illustrate how [[AM-HM]] is related to [[AM-GM]] and Cauchy.<br />
<br />
==== By AM-GM ====<br />
<br />
By applying [[AM-GM]] twice, we have<br />
<center><br />
<math><br />
[(b+c) + (c+a) + (a+b)] \left( \frac{1}{b+c} + \frac{1}{c+a} + \frac{1}{a+b} \right) \geq 3 [(b+c)(c+a)(a+b)]^{\frac{1}{3}} \cdot \left(\frac{1}{(b+c)(c+a)(a+b)}\right)^{\frac{1}{3}} = 9<br />
</math>,<br />
</center><br />
which yields the desired inequality.<br />
<br />
==== By Expansion and AM-GM ====<br />
<br />
We consider the equivalent inequality<br />
<center><br />
<math><br />
[(b+c) + (c+a) + (a+c)]\left( \frac{1}{b+c} + \frac{1}{c+a} + \frac{1}{a+b} \right) \geq 9<br />
</math>.<br />
</center><br />
Setting <math>x = b+c, y= c+a, z= a+b </math>, we expand the left side to obtain<br />
<center><br />
<math><br />
3 + \frac{x}{y} + \frac{y}{x} + \frac{y}{z} + \frac{z}{y} + \frac{z}{x} + \frac{x}{z} \geq 9<br />
</math>,<br />
</center><br />
which follows from <math> \frac{x}{y} + \frac{y}{x} \geq 2 </math>, etc., by [[AM-GM]], with equality when <math>x=y=z </math>.<br />
<br />
==== By AM-HM ====<br />
<br />
The [[AM-HM]] inequality for three variables,<br />
<center><br />
<math><br />
\frac{x+y+z}{3} \geq \frac{3}{\frac{1}{x} + \frac{1}{y} + \frac{1}{z}}<br />
</math>,<br />
</center><br />
is equivalent to<br />
<center><br />
<math><br />
(x+y+z) \left(\frac{1}{x} + \frac{1}{y} + \frac{1}{z}\right) \geq 9<br />
</math>.<br />
</center><br />
Setting <math>x=b+c, y=c+a, z=a+b </math> yields the desired inequality.<br />
<br />
=== By Substitution ===<br />
<br />
The numbers <math>x = \frac{a}{b+c}, y = \frac{b}{c+a}, z = \frac{c}{a+b} </math> satisfy the condition <math>xy + yz + zx + 2xyz = 1 </math>. Thus it is sufficient to prove that if any numbers <math>x,y,z </math> satisfy <math>xy + yz + zx + 2xyz = 1 </math>, then <math> x+y+z \geq \frac{3}{2} </math>.<br />
<br />
Suppose, on the contrary, that <math> x+y+z < \frac{3}{2} </math>. We then have <math>xy + yz + zx \leq \frac{(x+y+z)^2}{3} < \frac{3}{4} </math>, and <math> 2xyz \leq 2 \left( \frac{x+y+z}{3} \right)^3 < \frac{1}{4} </math>. Adding these inequalities yields <math>xy + yz + zx + 2xyz < 1 </math>, a contradiction.<br />
<br />
=== By Normalization and AM-HM ===<br />
<br />
We may normalize so that <math>a+b+c = 1 </math>. It is then sufficient to prove<br />
<center><br />
<math><br />
\frac{1}{b+c} + \frac{1}{c+a} + \frac{1}{a+b} \geq \frac{9}{2}<br />
</math>,<br />
</center><br />
which follows from [[AM-HM]].<br />
<br />
=== By Weighted AM-HM ===<br />
<br />
We may normalize so that <math>a+b+c =1 </math>.<br />
<br />
We first note that by the [[rearrangement inequality]] or the fact that <math>(a-b)^2 + (b-c)^2 + (c-a)^2 \geq 0</math>,<br />
<center><br />
<math><br />
3 (ab + bc + ca) \leq a^2 + b^2 + c^2 + 2(ab + bc + ca) <br />
</math>,<br />
</center><br />
so<br />
<center><br />
<math><br />
\frac{1}{a(b+c) + b(c+a) + c(a+b)} \geq \frac{1}{\frac{2}{3}(a+b+c)^2} = \frac{3}{2}<br />
</math>.<br />
</center><br />
<br />
Since <math>a+b+c = 1 </math>, weighted AM-HM gives us<br />
<center><br />
<math><br />
a\cdot \frac{1}{b+c} + b \cdot \frac{1}{c+a} + c \cdot \frac{1}{a+b} \geq \frac{1}{a(b+c) + b(c+a) + c(a+b)} \geq \frac{3}{2}<br />
</math>.<br />
</center><br />
<br />
===By Muirhead's and Cauchy===<br />
<br />
By Cauchy, <cmath>\sum_{\text{cyc}}\frac{a^2}{ab + ac} \geq \frac{(a + b + c)^2}{2(ab + ac + bc)} = \frac{a^2 + b^2 + c^2 + 2(ab + ac + bc)}{2(ab + ac + bc)}</cmath> <cmath> = 1 + \frac{a^2 + b^2 + c^2}{2(ab + ac + bc)} \geq \frac{3}{2}</cmath> since <math>a^2 + b^2 + c^2 \geq ab + ac + bc</math> by Muirhead as <math>[1, 1, 0]\prec [2, 0, 0]</math><br />
<br />
===Another Interesting Method===<br />
<br />
Let <cmath>S=\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}</cmath><br />
And <cmath>M=\frac{b}{b+c}+\frac{c}{c+a}+\frac{a}{a+b}</cmath><br />
And <cmath>N=\frac{c}{b+c}+\frac{a}{c+a}+\frac{b}{a+b}</cmath><br />
Now, we get <cmath>M+N=3</cmath><br />
Also by AM-GM; <cmath>M+S\geq 3</cmath> and <cmath>N+S\geq 3</cmath><br />
<cmath>\implies M+N+2S\geq 6</cmath><br />
<cmath>\implies 2S\geq 3</cmath><br />
<cmath>\implies S\geq \frac{3}{2}</cmath><br />
<br />
===By Muirhead's and expansion===<br />
<br />
Let <math>[x,y,z]=\sum_{sym} a^xb^yc^z</math>. Expanding out we get that our inequality is equivalent to <cmath>\sum_{cyc} a^3+\sum_{sym} a^2b+\sum_{cyc} abc \geq \frac{3(a+b)(b+c)(c+a)}{2}</cmath> This means <cmath>[3,0,0]/2+[2,1,0]+[1,1,1]/2\geq \frac{3}{2}(a+b)(b+c)(a+c)</cmath> So it follows that we must prove <cmath>[3,0,0]+2[2,1,0]+[1,1,1]\geq 3([2,1,0]+[1,1,1]/3)</cmath> So it follows that we must prove <math>[3,0,0]\geq [2,1,0]</math> which immediately follows from Muirhead's.<br />
[[Category:Inequality]]<br />
[[Category:Theorems]]</div>Sirhcgninilhttps://artofproblemsolving.com/wiki/index.php?title=Nesbitt%27s_Inequality&diff=105469Nesbitt's Inequality2019-04-23T15:44:17Z<p>Sirhcgninil: </p>
<hr />
<div>'''Nesbitt's [[Inequality]]''' is a theorem which, although rarely cited, has many instructive proofs. It states that for positive <math>a, b, c </math>,<br />
<center><br />
<math><br />
\frac{a}{b+c} + \frac{b}{c+a} + \frac{c}{a+b} \ge \frac{3}{2}<br />
</math>,<br />
</center><br />
with equality when all the variables are equal.<br />
<br />
All of the proofs below generalize to proof the following more general inequality.<br />
<br />
If <math> a_1, \ldots a_n </math> are positive and <math> \sum_{i=1}^{n}a_i = s </math>, then <br />
<center><br />
<math><br />
\sum_{i=1}^{n}\frac{a_i}{s-a_i} \geq \frac{n}{n-1}<br />
</math>,<br />
</center><br />
or equivalently<br />
<center><br />
<math><br />
\sum_{i=1}^{n}\frac{s}{s-a_i} \ge \frac{n^2}{n-1}<br />
</math>,<br />
</center><br />
with equality when all the <math>a_i </math> are equal.<br />
<br />
== Proofs ==<br />
<br />
=== By Rearrangement ===<br />
<br />
Note that <math>a,b,c </math> and <math> \frac{1}{b+c} = \frac{1}{a+b+c -a}</math>, <math> \frac{1}{c+a} = \frac{1}{a+b+c -b} </math>, <math> \frac{1}{a+b} = \frac{1}{a+b+c -c} </math> are sorted in the same order. Then by the [[rearrangement inequality]],<br />
<center><br />
<math><br />
2 \left( \frac{a}{b+c} + \frac{b}{c+a} + \frac{c}{a+b} \right) \ge \frac{b}{b+c} + \frac{c}{b+c} + \frac{c}{c+a} + \frac{a}{c+a} + \frac{a}{a+b} + \frac{b}{a+b} = 3<br />
</math>.<br />
</center><br />
For equality to occur, since we changed <math>{} a \cdot \frac{1}{b+c} + b \cdot \frac{1}{c+a} </math> to <math> b \cdot \frac{1}{b+c} + a \cdot \frac{1}{c+a} </math>, we must have <math>a=b </math>, so by symmetry, all the variables must be equal.<br />
<br />
=== By Cauchy ===<br />
<br />
By the [[Cauchy-Schwarz Inequality]], we have<br />
<center><br />
<math><br />
[(b+c) + (c+a) + (a+b)]\left( \frac{1}{b+c} + \frac{1}{c+a} + \frac{1}{a+b} \right) \geq 9<br />
</math>,<br />
</center><br />
or<br />
<center><br />
<math><br />
2\left( \frac{a+b+c}{b+c} + \frac{a+b+c}{c+a} + \frac{a+b+c}{a+b} \right) \geq 9<br />
</math>,<br />
</center><br />
as desired. Equality occurs when <math>(b+c)^2 = (c+a)^2 = (a+b)^2 </math>, i.e., when <math>a=b=c </math>.<br />
<br />
We also present three closely related variations of this proof, which illustrate how [[AM-HM]] is related to [[AM-GM]] and Cauchy.<br />
<br />
==== By AM-GM ====<br />
<br />
By applying [[AM-GM]] twice, we have<br />
<center><br />
<math><br />
[(b+c) + (c+a) + (a+b)] \left( \frac{1}{b+c} + \frac{1}{c+a} + \frac{1}{a+b} \right) \geq 3 [(b+c)(c+a)(a+b)]^{\frac{1}{3}} \cdot \left(\frac{1}{(b+c)(c+a)(a+b)}\right)^{\frac{1}{3}} = 9<br />
</math>,<br />
</center><br />
which yields the desired inequality.<br />
<br />
==== By Expansion and AM-GM ====<br />
<br />
We consider the equivalent inequality<br />
<center><br />
<math><br />
[(b+c) + (c+a) + (a+c)]\left( \frac{1}{b+c} + \frac{1}{c+a} + \frac{1}{a+b} \right) \geq 9<br />
</math>.<br />
</center><br />
Setting <math>x = b+c, y= c+a, z= a+b </math>, we expand the left side to obtain<br />
<center><br />
<math><br />
3 + \frac{x}{y} + \frac{y}{x} + \frac{y}{z} + \frac{z}{y} + \frac{z}{x} + \frac{x}{z} \geq 9<br />
</math>,<br />
</center><br />
which follows from <math> \frac{x}{y} + \frac{y}{x} \geq 2 </math>, etc., by [[AM-GM]], with equality when <math>x=y=z </math>.<br />
<br />
==== By AM-HM ====<br />
<br />
The [[AM-HM]] inequality for three variables,<br />
<center><br />
<math><br />
\frac{x+y+z}{3} \geq \frac{3}{\frac{1}{x} + \frac{1}{y} + \frac{1}{z}}<br />
</math>,<br />
</center><br />
is equivalent to<br />
<center><br />
<math><br />
(x+y+z) \left(\frac{1}{x} + \frac{1}{y} + \frac{1}{z}\right) \geq 9<br />
</math>.<br />
</center><br />
Setting <math>x=b+c, y=c+a, z=a+b </math> yields the desired inequality.<br />
<br />
=== By Substitution ===<br />
<br />
The numbers <math>x = \frac{a}{b+c}, y = \frac{b}{c+a}, z = \frac{c}{a+b} </math> satisfy the condition <math>xy + yz + zx + 2xyz = 1 </math>. Thus it is sufficient to prove that if any numbers <math>x,y,z </math> satisfy <math>xy + yz + zx + 2xyz = 1 </math>, then <math> x+y+z \geq \frac{3}{2} </math>.<br />
<br />
Suppose, on the contrary, that <math> x+y+z < \frac{3}{2} </math>. We then have <math>xy + yz + zx \leq \frac{(x+y+z)^2}{3} < \frac{3}{4} </math>, and <math> 2xyz \leq 2 \left( \frac{x+y+z}{3} \right)^3 < \frac{1}{4} </math>. Adding these inequalities yields <math>xy + yz + zx + 2xyz < 1 </math>, a contradiction.<br />
<br />
=== By Normalization and AM-HM ===<br />
<br />
We may normalize so that <math>a+b+c = 1 </math>. It is then sufficient to prove<br />
<center><br />
<math><br />
\frac{1}{b+c} + \frac{1}{c+a} + \frac{1}{a+b} \geq \frac{9}{2}<br />
</math>,<br />
</center><br />
which follows from [[AM-HM]].<br />
<br />
=== By Weighted AM-HM ===<br />
<br />
We may normalize so that <math>a+b+c =1 </math>.<br />
<br />
We first note that by the [[rearrangement inequality]] or the fact that <math>(a-b)^2 + (b-c)^2 + (c-a)^2 \geq 0</math>,<br />
<center><br />
<math><br />
3 (ab + bc + ca) \leq a^2 + b^2 + c^2 + 2(ab + bc + ca) <br />
</math>,<br />
</center><br />
so<br />
<center><br />
<math><br />
\frac{1}{a(b+c) + b(c+a) + c(a+b)} \geq \frac{1}{\frac{2}{3}(a+b+c)^2} = \frac{3}{2}<br />
</math>.<br />
</center><br />
<br />
Since <math>a+b+c = 1 </math>, weighted AM-HM gives us<br />
<center><br />
<math><br />
a\cdot \frac{1}{b+c} + b \cdot \frac{1}{c+a} + c \cdot \frac{1}{a+b} \ge \frac{1}{a(b+c) + b(c+a) + c(a+b)} \geq \frac{3}{2}<br />
</math>.<br />
</center><br />
<br />
===By Muirhead's and Cauchy===<br />
<br />
By Cauchy, <cmath>\sum_{\text{cyc}}\frac{a^2}{ab + ac} \ge \frac{(a + b + c)^2}{2(ab + ac + bc)} = \frac{a^2 + b^2 + c^2 + 2(ab + ac + bc)}{2(ab + ac + bc)}</cmath> <cmath> = 1 + \frac{a^2 + b^2 + c^2}{2(ab + ac + bc)} \ge \frac{3}{2}</cmath> since <math>a^2 + b^2 + c^2 \ge ab + ac + bc</math> by Muirhead as <math>[1, 1, 0]\prec [2, 0, 0]</math><br />
<br />
===Another Interesting Method===<br />
<br />
Let <cmath>S=\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}</cmath><br />
And <cmath>M=\frac{b}{b+c}+\frac{c}{c+a}+\frac{a}{a+b}</cmath><br />
And <cmath>N=\frac{c}{b+c}+\frac{a}{c+a}+\frac{b}{a+b}</cmath><br />
Now, we get <cmath>M+N=3</cmath><br />
Also by AM-GM; <cmath>M+S\geq 3</cmath> and <cmath>N+S\geq 3</cmath><br />
<cmath>\implies M+N+2S\geq 6</cmath><br />
<cmath>\implies 2S\geq 3</cmath><br />
<cmath>\implies S\geq \frac{3}{2}</cmath><br />
<br />
===By Muirhead's and expansion===<br />
<br />
Let <math>[x,y,z]=\sum_{sym} a^xb^yc^z</math>. Expanding out we get that our inequality is equivalent to <cmath>\sum_{cyc} a^3+\sum_{sym} a^2b+\sum_{cyc} abc \geq \frac{3(a+b)(b+c)(c+a)}{2}</cmath> This means <cmath>[3,0,0]/2+[2,1,0]+[1,1,1]/2\geq \frac{3}{2}(a+b)(b+c)(a+c)</cmath> So it follows that we must prove <cmath>[3,0,0]+2[2,1,0]+[1,1,1]\geq 3([2,1,0]+[1,1,1]/3)</cmath> So it follows that we must prove <math>[3,0,0]\geq[2,1,0]</math> which immediately follows from Muirhead's.<br />
[[Category:Inequality]]<br />
[[Category:Theorems]]</div>Sirhcgninilhttps://artofproblemsolving.com/wiki/index.php?title=2014_Canadian_MO_Problems/Problem_1&diff=1049902014 Canadian MO Problems/Problem 12019-03-28T15:54:03Z<p>Sirhcgninil: </p>
<hr />
<div>== Problem 1 ==<br />
Let <math>a_1,a_2,\dots,a_n</math> be positive real numbers whose product is <math>1</math>. Show that the sum <math>\textstyle\frac{a_1}{1+a_1}+\frac{a_2}{(1+a_1)(1+a_2)}+\frac{a_3}{(1+a_1)(1+a_2)(1+a_3)}+\cdots+\frac{a_n}{(1+a_1)(1+a_2)\cdots(1+a_n)}</math> is greater than or equal to <math>\frac{2^n-1}{2^n}</math>.<br />
== Solution ==<br />
<math>\frac{a_1}{1+a_1}+\frac{a_2}{(1+a_1)(1+a_2)}+\cdots+\frac{a_n}{(1+a_1)(1+a_2)\cdots (1+a_n)}\\=(1-\frac{1}{1+a_1})+(\frac{1}{1+a_1}-\frac{1}{(1+a_1)(1+a_2)})+\cdots+(\frac{1}{(1+a_1)(1+a_2)\cdots (1+a_{n-1})}-\frac{1}{(1+a_1)(1+a_2)\cdots (1+a_n)})\\=1-\frac{1}{(1+a_1)(1+a_2)\cdots (1+a_n)}\\\geq 1-\frac{1}{(2\sqrt{1\cdot a_1)}(2\sqrt{1\cdot a_2)}\cdots (2\sqrt{1\cdot a_n)}}\\=1-\frac{1}{2^n}\\=\frac{2^n-1}{2^n}</math></div>Sirhcgninilhttps://artofproblemsolving.com/wiki/index.php?title=2014_Canadian_MO_Problems/Problem_1&diff=1049792014 Canadian MO Problems/Problem 12019-03-27T12:43:57Z<p>Sirhcgninil: </p>
<hr />
<div><math>\frac{a_1}{1+a_1}+\frac{a_2}{(1+a_1)(1+a_2)}+\cdots+\frac{a_n}{(1+a_1)(1+a_2)\cdots (1+a_n)}\\=(1-\frac{1}{1+a_1})+(\frac{1}{1+a_1}-\frac{1}{(1+a_1)(1+a_2)})+\cdots+(\frac{1}{(1+a_1)(1+a_2)\cdots (1+a_{n-1})}-\frac{1}{(1+a_1)(1+a_2)\cdots (1+a_n)})\\=1-\frac{1}{(1+a_1)(1+a_2)\cdots (1+a_n)}\\\geq 1-\frac{1}{(2\sqrt{1\cdot a_1)}(2\sqrt{1\cdot a_2)}\cdots (2\sqrt{1\cdot a_n)}}\\=1-\frac{1}{2^n}\\=\frac{2^n-1}{2^n}</math></div>Sirhcgninilhttps://artofproblemsolving.com/wiki/index.php?title=2014_Canadian_MO_Problems/Problem_1&diff=1049782014 Canadian MO Problems/Problem 12019-03-27T12:43:16Z<p>Sirhcgninil: </p>
<hr />
<div><math>\frac{a_1}{1+a_1}</math>+<math>\frac{a_2}{(1+a_1)(1+a_2)}+\cdots+\frac{a_n}{(1+a_1)(1+a_2)\cdots (1+a_n)}\\=(1-\frac{1}{1+a_1})+(\frac{1}{1+a_1}-\frac{1}{(1+a_1)(1+a_2)})+\cdots+(\frac{1}{(1+a_1)(1+a_2)\cdots (1+a_{n-1})}-\frac{1}{(1+a_1)(1+a_2)\cdots (1+a_n)})\\=1-\frac{1}{(1+a_1)(1+a_2)\cdots (1+a_n)}\\\geq 1-\frac{1}{(2\sqrt{1\cdot a_1)}(2\sqrt{1\cdot a_2)}\cdots (2\sqrt{1\cdot a_n)}}\\=1-\frac{1}{2^n}\\=\frac{2^n-1}{2^n}</math></div>Sirhcgninilhttps://artofproblemsolving.com/wiki/index.php?title=2014_Canadian_MO_Problems/Problem_1&diff=1049652014 Canadian MO Problems/Problem 12019-03-26T13:45:01Z<p>Sirhcgninil: </p>
<hr />
<div>[code]<br />
\begin{math}<br />
\frac{a_1}{1+a_1}+\frac{a_2}{(1+a_1)(1+a_2)}+\cdots+\frac{a_n}{(1+a_1)(1+a_2)\cdots (1+a_n)}\\=(1-\frac{1}{1+a_1})+(\frac{1}{1+a_1}-\frac{1}{(1+a_1)(1+a_2)})+\cdots+(\frac{1}{(1+a_1)(1+a_2)\cdots (1+a_{n-1})}-\frac{1}{(1+a_1)(1+a_2)\cdots (1+a_n)})\\=1-\frac{1}{(1+a_1)(1+a_2)\cdots (1+a_n)}\\\geq 1-\frac{1}{(2\sqrt{1\cdot a_1)}(2\sqrt{1\cdot a_2)}\cdots (2\sqrt{1\cdot a_n)}}\\=1-\frac{1}{2^n}\\=\frac{2^n-1}{2^n}<br />
\end{math}</div>Sirhcgninilhttps://artofproblemsolving.com/wiki/index.php?title=2014_Canadian_MO_Problems/Problem_1&diff=1049642014 Canadian MO Problems/Problem 12019-03-26T13:19:43Z<p>Sirhcgninil: </p>
<hr />
<div>[code]<br />
\begin{align*}<br />
\frac{a_1}{1+a_1}+\frac{a_2}{(1+a_1)(1+a_2)}+\cdots+\frac{a_n}{(1+a_1)(1+a_2)\cdots (1+a_n)}\\=(1-\frac{1}{1+a_1})+(\frac{1}{1+a_1}-\frac{1}{(1+a_1)(1+a_2)})+\cdots+(\frac{1}{(1+a_1)(1+a_2)\cdots (1+a_{n-1})}-\frac{1}{(1+a_1)(1+a_2)\cdots (1+a_n)})\\=1-\frac{1}{(1+a_1)(1+a_2)\cdots (1+a_n)}\\\geq 1-\frac{1}{(2\sqrt{1\cdot a_1)}(2\sqrt{1\cdot a_2)}\cdots (2\sqrt{1\cdot a_n)}}\\=1-\frac{1}{2^n}\\=\frac{2^n-1}{2^n}<br />
\end{align*}</div>Sirhcgninilhttps://artofproblemsolving.com/wiki/index.php?title=2014_Canadian_MO_Problems/Problem_1&diff=1049632014 Canadian MO Problems/Problem 12019-03-26T13:14:31Z<p>Sirhcgninil: Created page with "\begin{align*} \frac{a_1}{1+a_1}+\frac{a_2}{(1+a_1)(1+a_2)}+\cdots+\frac{a_n}{(1+a_1)(1+a_2)\cdots (1+a_n)}\\=(1-\frac{1}{1+a_1})+(\frac{1}{1+a_1}-\frac{1}{(1+a_1)(1+a_2)})+\c..."</p>
<hr />
<div>\begin{align*}<br />
\frac{a_1}{1+a_1}+\frac{a_2}{(1+a_1)(1+a_2)}+\cdots+\frac{a_n}{(1+a_1)(1+a_2)\cdots (1+a_n)}\\=(1-\frac{1}{1+a_1})+(\frac{1}{1+a_1}-\frac{1}{(1+a_1)(1+a_2)})+\cdots+(\frac{1}{(1+a_1)(1+a_2)\cdots (1+a_{n-1})}-\frac{1}{(1+a_1)(1+a_2)\cdots (1+a_n)})\\=1-\frac{1}{(1+a_1)(1+a_2)\cdots (1+a_n)}\\\geq 1-\frac{1}{(2\sqrt{1\cdot a_1)}(2\sqrt{1\cdot a_2)}\cdots (2\sqrt{1\cdot a_n)}}\\=1-\frac{1}{2^n}\\=\frac{2^n-1}{2^n}<br />
\end{align*}</div>Sirhcgninil