|
|
| Line 1: |
Line 1: |
| | ==Problem== | | ==Problem== |
| − | A graph is <math>\textit{symmetric}</math> about a line if the graph remains unchanged after reflection in that line. For how many quadruples of integers <math>(a, b, c, d)</math>, where <math>|a|, |b|, |c|, |d| \leq 5</math> and <math>c</math> and <math>d</math> are not both <math>0</math>, is the graph of <cmath>y =\frac{ax + b}{cx + d}</cmath> symmetric about the line <math>y = x</math>?
| + | Suppose that <math>a_1 = 2</math> and the sequence <math>(a_n)</math> satisfies the recurrence relation <cmath>\frac{a_n -1}{n-1}=\frac{a_{n-1}+1}{(n-1)+1}</cmath>for all <math>n \ge 2.</math> What is the greatest integer less than or equal to <cmath>\sum^{100}_{n=1} a_n^2?</cmath> |
| | | | |
| − | <math>\textbf{(A)}~1282\qquad\textbf{(B)}~1292\qquad\textbf{(C)}~1310\qquad\textbf{(D)}~1320\qquad\textbf{(E)}~1330</math> | + | <math>\textbf{(A) } 338{,}550 \qquad \textbf{(B) } 338{,}551 \qquad \textbf{(C) } 338{,}552 \qquad \textbf{(D) } 338{,}553 \qquad \textbf{(E) } 338{,}554</math> |
| | | | |
| − | ==Solution 1 (Inverse Function)== | + | ==Solution 1== |
| − | Symmetric about the line <math>y=x</math> implies that the inverse function <math>y^{-1}=y</math>. Then we split the question into several cases to find the final answer.
| + | Multiply both sides of the recurrence to find that <math>n(a_n-1)=(n-1)(a_{n-1}+1)=(n-1)(a_{n-1}-1)+(n-1)(2)</math>. |
| | | | |
| | + | Let <math>b_n=n(a_n-1)</math>. Then the previous relation becomes |
| | + | <cmath>b_n=b_{n-1}+2(n-1)</cmath> |
| | | | |
| | + | We can rewrite this relation for values of <math>n</math> until <math>1</math> and use telescoping to derive an explicit formula: |
| | | | |
| − | Case 1: <math>c=0</math>
| + | <cmath>b_n=b_{n-1}+2(n-1)</cmath> |
| | + | <cmath>b_{n-1}=b_{n-2}+2(n-2)</cmath> |
| | + | <cmath>b_{n-2}=b_{n-3}+2(n-3)</cmath> |
| | + | <cmath>\cdot</cmath> |
| | + | <cmath>\cdot</cmath> |
| | + | <cmath>\cdot</cmath> |
| | + | <cmath>b_2=b_1+2(1)</cmath> |
| | | | |
| − | Then <math>y=\frac{a}{d}x+\frac{b}{d}</math> and <math>y^{-1}=\frac{d}{a}x-\frac{b}{a}</math>.
| + | Summing the equations yields: |
| − | Giving us <math>\frac{a}{d}=\frac{d}{a}</math> and <math>\frac{b}{d}=-\frac{b}{a}</math>
| |
| | | | |
| − | Therefore, we obtain 2 subcases: <math>b\neq 0, a+d=0</math> and <math>b=0, a^2=d^2</math>
| + | <cmath>b_n+b_{n-1}+\cdots+b_2=b_{n-1}+b_{n-2}+\cdots+b_1+2((n-1)+(n-2)+\cdots+1)</cmath> |
| | + | <cmath>b_n-b_1=2\cdot\frac{n(n-1)}{2}</cmath> |
| | + | <cmath>b_n-1=n(n-1)</cmath> |
| | + | <cmath>b_n=n(n-1)+1</cmath> |
| | | | |
| | + | Now we can substitute <math>a_n</math> back into our equation: |
| | | | |
| | + | <cmath>n(a_n-1)=n(n-1)+1</cmath> |
| | + | <cmath>a_n-1=n-1+\frac{1}{n}</cmath> |
| | + | <cmath>a_n=n+\frac{1}{n}</cmath> |
| | + | <cmath>a_n^2=n^2+\frac{1}{n^2}+2</cmath> |
| | | | |
| − | Case 2: <math>c\neq 0</math>
| + | Thus the sum becomes |
| | | | |
| − | Then <math>y^{-1}=\frac{b-dx}{cx-a}=\frac{(cx-a)(-\frac{d}{c})+b-\frac{ad}{c}}{cx-a}=-\frac{d}{c}+\frac{b-\frac{ad}{c}}{cx-a}</math>
| + | <cmath>\sum^{100}_{n=1} a_n^2= \sum^{100}_{n=1} n^2+ \sum^{100}_{n=1} \frac{1}{n^2}+ \sum^{100}_{n=1} 2</cmath> |
| | | | |
| − | And <math>y=\frac{(cx+d)(\frac{a}{c})+b-\frac{ad}{c}}{cx+d}=\frac{a}{c}+\frac{b-\frac{ad}{c}}{cx+d}</math>
| + | We know that <math>\sum^{100}_{n=1} n^2=\frac{100\cdot101\cdot201}{6}=338350</math>, and we also know that <math>\sum^{100}_{n=1} 2=200</math>, so the requested sum is equivalent to <math>\sum^{100}_{n=1} \frac{1}{n^2}+338550</math>. All that remains is to calculate <math>\sum^{100}_{n=1} \frac{1}{n^2}</math>, and we know that this value lies between <math>1</math> and <math>2</math> (see the note below for a proof). Thus, |
| | | | |
| − | So <math>\frac{a}{c}=-\frac{d}{c}</math>, or <math>a=-d</math> (<math>c\neq 0</math>), and substitute that into <math>\frac{b-\frac{ad}{c}}{cx-a}=\frac{b-\frac{ad}{c}}{cx+d}</math> gives us:
| + | <cmath>\sum^{100}_{n=1} a_n^2= \sum^{100}_{n=1} \frac{1}{n^2}+338550<2+338550=338552</cmath> |
| − | | + | <cmath>\sum^{100}_{n=1} a_n^2= \sum^{100}_{n=1} \frac{1}{n^2}+338550>1+338550=338551</cmath> |
| − | <math>bc-ad\neq 0</math> (Otherwise <math>y=\frac{a}{c}</math>, <math>y^{-1}=-\frac{d}{c}=\frac{a}{c}</math>, and is not symmetric about <math>y=x</math>) | |
| − | | |
| − | | |
| − | | |
| − | Therefore we get three cases:
| |
| − | | |
| − | Case 1.1: <math>c= 0, b\neq 0, d\neq 0, a+d=0</math>
| |
| − | | |
| − | We have 10 choice of <math>b</math>, 10 choice of <math>d</math> and each choice of <math>d</math> has one corresponding choice of <math>a</math>. In total <math>10\times 10=100</math> ways.
| |
| | | | |
| | + | so |
| | | | |
| | + | <cmath>\sum^{100}_{n=1} a_n^2\in(338551,338552)</cmath> |
| | | | |
| − | Case 1.2: <math>c= 0, b = 0, d\neq 0, a^2=d^2</math>
| + | and thus the answer is <math>\boxed{\textbf{(B) }338551}</math>. |
| | | | |
| − | We have 10 choice for <math>d</math> (<math>d\neq 0</math>), each choice of <math>d</math> has 2 corresponding choice of <math>a</math>, thus <math>10\times 2=20</math> ways.
| + | ~eevee9406 |
| | | | |
| | + | <b>Note:</b> <math>\sum^{100}_{n=1} \frac{1}{n^2}< \sum^{\infty}_{n=1} \frac{1}{n^2}=\frac{\pi^2}{6}<2</math>. It is obvious that the sum is greater than 1 (since it contains <math>\frac{1}{1^2}</math> as one of its terms). |
| | | | |
| | + | If you forget this and have to derive this on the exam, here is how: |
| | | | |
| − | Case 2: <math>c\neq 0, bc-ad\neq 0, a=-d</math>
| + | <cmath>\sum^{100}_{n=1} \frac{1}{n^2}<\sum^{\infty}_{n=1} \frac{1}{n^2}=\frac{1}{1^1}+\left(\frac{1}{2^2}+\frac{1}{3^2}\right)+\left(\frac{1}{4^2}+\frac{1}{5^2}+\frac{1}{6^2}+\frac{1}{7^2}\right)+\cdots</cmath> |
| | | | |
| − | <math>a=0</math>: <math>10\times 10=100</math> ways. | + | <cmath><1+\left(\frac{1}{2^2}+\frac{1}{2^2}\right)+\left(\frac{1}{4^2}+\frac{1}{4^2}+\frac{1}{4^2}+\frac{1}{4^2}\right)+\left(\frac{1}{8^2}+\frac{1}{8^2}+\frac{1}{8^2}+\frac{1}{8^2}+\frac{1}{8^2}+\frac{1}{8^2}+\frac{1}{8^2}+\frac{1}{8^2}\right)+\cdots</cmath> |
| | | | |
| − | <math>a=\pm 1</math>: <math>(11\times 10-2)\times 2=216</math> ways. | + | <cmath>=1+\frac{2}{2^2}+\frac{4}{4^2}+\frac{8}{8^2}+\cdots</cmath> |
| | | | |
| − | <math>a=\pm 2</math>: <math>(11\times 10-2)\times 2=216</math> ways. | + | <cmath>=1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots=2</cmath> |
| | | | |
| − | <math>a=\pm 3</math>: <math>(11\times 10-2)\times 2=216</math> ways. | + | and it is clear that <math>\sum^{100}_{n=1} \frac{1}{n^2}<2</math>. ~eevee9406 |
| | | | |
| − | <math>a=\pm 4</math>: <math>(11\times 10-6)\times 2=208</math> ways.
| |
| | | | |
| − | <math>a=\pm 5</math>: <math>(11\times 10-2)\times 2=216</math> ways.
| + | ==Solution 2== |
| | + | According to the equation given, |
| | | | |
| − | In total <math>100+208+216\times 4= 1172</math> ways.
| + | <cmath>\frac{a_n - 1}{n - 1} = \frac{a_{n - 1} + 1}{n}</cmath> |
| | | | |
| | + | <cmath>na_n - n = (n - 1)a_{n - 1} + n - 1</cmath> |
| | | | |
| | + | <cmath>na_n - (n - 1)a_{n - 1} = 2n - 1</cmath> |
| | | | |
| − | So the answer is <math>100+20+1172= \boxed{\textbf{(B) }1292}</math>
| + | Suppose <math>\{b_n\}</math>, <math>b_n = na_n</math>, then <math>b_n - b_{n - 1} = 2n - 1</math>, where <math>b_1 = 1 \cdot a_1 = 2</math>, then we obtain that |
| | | | |
| − | ~ERiccc
| + | <cmath>b_n = b_1 + (b_2 - b_1) + (b_3 - b_2) + \cdots + (b_n - b_{n - 1})</cmath> |
| | | | |
| − | ==Solution 2 (Rotation + Edge Cases)== | + | <cmath>b_n = 2 + 3 + 5 + \cdots + (2n - 1) = 1 + n^2</cmath> |
| − | First, observe that the only linear functions that are symmetric about <math>y = x</math> are <math>y = x</math> and <math>y = -x+k</math>, where <math>k</math> is some constant.
| |
| | | | |
| | + | <cmath>a_n = \frac{1 + n^2}{n} = n + \frac{1}{n}</cmath> |
| | | | |
| | + | Hence, |
| | | | |
| − | We perform a <math>45^\circ</math> counterclockwise rotation of the Cartesian plane. Let <math>(x, y)</math> be sent to <math>(u, v)</math>. Then <math>u</math> and <math>v</math> are the real and imaginary parts of <math>(x + yi)(\frac{\sqrt{2}}{2}+\frac{\sqrt{2}}{2}i)</math> respectively, which gives
| + | <cmath> |
| | + | \begin{align*} |
| | + | \sum_{n = 1}^{100} a_n^2 &= \sum_{n = 1}^{100} \left(n + \frac{1}{n}\right)^2\\ |
| | + | &= \sum_{n = 1}^{100} (n^2 + 2 + \frac{1}{n^2})\\ |
| | + | &= \sum_{n = 1}^{100} n^2 + \sum_{n = 1}^{100} 2 + \sum_{n = 1}^{100}\frac{1}{n^2}\\ |
| | + | &= \frac{1}{6} \cdot 100 \cdot (100 + 1) \cdot (100 \cdot 2 + 1) + 100 \cdot 2 + \sum_{n = 1}^{100}\frac{1}{n^2}\\ |
| | + | &= 338350 + 200 + \sum_{n = 1}^{100}\frac{1}{n^2}\\ |
| | + | &= 338550 + \sum_{n = 1}^{100}\frac{1}{n^2} |
| | + | \end{align*} |
| | + | </cmath> |
| | | | |
| − | <cmath>u = \frac{x - y}{\sqrt{2}}</cmath> | + | Notice that, |
| − | <cmath>v = \frac{x + y}{\sqrt{2}}</cmath> | + | <cmath>\sum_{n = 1}^{100}\frac{1}{n^2} = 1 + \sum_{n = 2}^{100}\frac{1}{n^2} > 1</cmath> |
| | + | <cmath>\sum_{n = 1}^{100}\frac{1}{n^2} < 1 + \sum_{n = 2}^{100}\frac{1}{n(n - 1)} = 1 + 1 - \frac{1}{100} < 2~~(\text{telescope})</cmath> |
| | | | |
| | so | | so |
| | | | |
| − | <cmath>x = \frac{v + u}{\sqrt{2}}</cmath> | + | <cmath>\sum^{100}_{n=1} a_n^2\in(338551,338552)</cmath> |
| − | <cmath>y = \frac{v - u}{\sqrt{2}}</cmath>.
| |
| − | | |
| − | The rotated function is symmetric about the y-axis, so the equation holds after replacing all instances of <math>u</math> with <math>-u</math> (this is just switching the values of <math>x</math> and <math>y</math> which is a reflection over <math>y = x</math>, but working in terms of <math>(u, v)</math> allows more cancellations in the following calculations).
| |
| − | | |
| − | Writing <math>x</math> and <math>y</math> in terms of <math>u</math> and <math>v</math>, we have
| |
| − | | |
| − | <cmath>\frac{v - u}{\sqrt{2}} = \frac{a(v + u) + b\sqrt{2}}{c(v + u) + d\sqrt{2}}</cmath>
| |
| − | <cmath>\frac{v + u}{\sqrt{2}} = \frac{a(v - u) + b\sqrt{2}}{c(v - u) + d\sqrt{2}}</cmath>
| |
| − | | |
| − | Multiplying both equations by <math>\sqrt{2}</math> and subtracting the second equation from the first equation gives <math>d = -a</math>. Since <math>a, b, c, d</math> are integers between <math>-5</math> and <math>5</math>, this gives <math>11^3 = 1331</math> combinations. We need to subtract the edge cases that don't work, namely all undefined functions and linear functions except <math>y = x</math> and <math>y = -x+k</math>. Consider the following cases:
| |
| − | | |
| − | | |
| − | | |
| − | Case 1: <math>a, b, c, d</math> are all nonzero. Then the function is linear when <math>ax + b</math> is a multiple of <math>cx + d</math>, or <math>\frac{a}{b} = \frac{c}{-a}</math>.
| |
| − | | |
| − | If <math>a = \pm 1</math>, <math>(b,c) = (1, -1)</math> or <math>(-1, 1)</math>; there are <math>2*2 = 4</math> ways.
| |
| − | | |
| − | If <math>a = \pm 2</math>, there are <math>12</math> ways.
| |
| − | | |
| − | If <math>a = \pm 3</math>, there are <math>4</math> ways.
| |
| − | | |
| − | If <math>a = \pm 4</math>, there are <math>4</math> ways.
| |
| − | | |
| − | If <math>a = \pm 5</math>, there are <math>4</math> ways.
| |
| − | | |
| − | In total, this case has <math>28</math> combinations.
| |
| − | | |
| − | | |
| − | | |
| − | Case 2: <math>a = b = d = 0</math> or <math>a = c = d = 0</math>
| |
| − | | |
| − | If <math>a = b = d = 0</math> then <math>c</math> can take on <math>11</math> values, and if <math>a = c = d = 0</math>, then <math>b</math> can take on <math>11</math> values, but <math>a = b = c = d = 0</math> is counted twice so this case has <math>11 + 11 - 1 = 21</math> combinations.
| |
| − | | |
| − | | |
| − | | |
| − | Finally, we need to add the case where <math>y = x</math>, which occurs when <math>a = d</math> and <math>b = c = 0</math>. <math>a</math> can be any integer from <math>-5</math> to <math>5</math> except <math>0</math>, so this case has <math>10</math> combinations. Since <math>y = -x+k</math> occurs when <math>a = -d</math> and <math>c = 0</math>, this case has already been counted.
| |
| − | | |
| − | | |
| − | | |
| − | Thus, the answer is <math>1331 - 28 - 21 + 10 = \boxed{\textbf{(B) }1292}</math>.
| |
| − | | |
| − | ~babyhamster
| |
| − | | |
| − | == Solution 3 (Asymptotes) ==
| |
| − | There are two cases: when <math>c=0</math> and when <math>c\neq 0</math>.
| |
| − | | |
| − | | |
| − | | |
| − | <math>\textbf{Case 1: }\mathbf{c=0.}</math> If <math>c=0</math>, then <math>y=\frac{ax+b}d=\frac adx+\frac bd</math>. This is the equation of a line, and the only lines symmetric about <math>y=x</math> are those perpendicular to <math>y=x</math> (i.e. those with slope <math>-1</math>) and <math>y=x</math> itself. To have a slope of <math>-1</math>, we need <math>a=-d\neq 0</math>, and <math>b</math> can be any of its <math>11</math> possibilities from <math>-5</math> to <math>5</math>. There are <math>11\cdot 10=110</math> possibilities here. For the function to be <math>y=x</math>, we need <math>a=d\neq 0</math> and <math>b=0</math>. There are <math>10</math> possibilities here. Thus, our total for Case 1 is <math>110+10=120</math> possiblities.
| |
| − | | |
| − | | |
| − | | |
| − | <math>\textbf{Case 2: }\mathbf{c\neq 0.}</math> When <math>c\neq 0</math>, we will first consider the case in which the graph is a hyperbola. Clearly, for this hyperbola to be symmetric about <math>y=x</math>, the intersection of its horizontal and vertical asymptotes must be on <math>y=x</math>. The location of the horizontal asymptote is <math>y=\frac ac</math>, and the vertical asymptote occurs at <math>x=-\frac dc</math>. These asymptotes intersect on <math>y=x</math> when <math>\frac ac = -\frac dc</math>, or, more simply, when <math>a=-d</math>.
| |
| − | | |
| − | If the asymptotes intersect on <math>y=x</math>, then the hyperbola must be symmetric about <math>y=x</math>. This is true because for any hyperbola with perpendicular asymptotes, we can rotate and translate the coordinate plane in a certain way such that that hyperbola has an equation of the form <math>x^2-y^2=a^2</math>. Then, the hyperbola's asymptotes would intersect at the origin, and it would be symmetric about the coordinate axes (because it makes a distinction neither between <math>x</math> and <math>-x</math> nor <math>y</math> and <math>-y</math>). The coordinate axes are the bisectors of the angles formed by the asymptotes, and the hyperbola is symmetric about them. Thus, because the angles formed by our hyperbola's asymptotes are bisected by <math>y=x</math>, our hyperbola must be symmetric about <math>y=x</math>.
| |
| − | | |
| − | Thus, with the conditions that <math>a=-d</math> and <math>c\neq 0</math>, there are <math>11\cdot 11\cdot 10\cdot 1=1210</math> possibilites for <math>(a,b,c,d)</math>. However, not all of these ordered quadruples produce hyperbolas. If <math>b=a=d=0</math> or <math>\frac ac=\frac bd</math>, then the quadruples produce horizontal lines with a hole when the denominator equals <math>0</math>. As seen in Case 1, these lines, with slope <math>0</math>, cannot be symmetric about <math>y=x</math>.
| |
| − | | |
| − | For the subcase where <math>b=a=d=0</math>, there are <math>10</math> possibilities for <math>c\neq 0</math>, which gives us <math>10</math> wrongly counted quadruples.
| |
| − | | |
| − | For the subcase where <math>\frac ac=\frac bd</math>, we wrongly counted cases where <math>d=-a</math>. Here, <math>-a^2=bc</math> by cross-multiplication. The casework on the possible values of <math>a</math> below counts the number of triples <math>(a,b,c)</math> with <math>|a|,|b|,|c|\leq 5</math> which satisfy this condition.
| |
| − | | |
| − | If <math>a=\pm 1</math>, <math>bc=-1</math>, which yields <math>2\cdot 2 \cdot 1=4</math> possibilities.
| |
| − | | |
| − | If <math>a=\pm 2</math>, <math>bc=-4</math>, which yields <math>2\cdot 2\cdot 3=12</math> possibilities.
| |
| − | | |
| − | If <math>a=\pm 3</math>, <math>bc=-9</math>, which yields <math>2\cdot 2\cdot 1=4</math> possbilities. (recall that <math>|b|,|c|\leq 5</math>)
| |
| − | | |
| − | If <math>a=\pm 4</math>, <math>bc=-16</math>, which yields <math>2\cdot 2\cdot 1=4</math> possibilities.
| |
| − | | |
| − | If <math>a=\pm 5</math>, <math>bc=-25</math>, which yields <math>2\cdot 2\cdot 1=4</math> possibilities.
| |
| − | | |
| − | Adding the above values together for this subcase yields <math>4+12+4+4+4=28</math> wrongly counted quadruples.
| |
| − | | |
| − | Subtracting the wrongly counted quadruples from our count for Case 2 yields <math>1210-10-28=1172</math>.
| |
| − | | |
| − | Adding the possibilities for Case 1 and Case 2 yields our final answer of <math>120+1172=\boxed{\textbf{(B) }1292}</math> possible quadruples.
| |
| − | | |
| − | == Solution 4 ==
| |
| − | Note that the condition is equivalent to having <math>f(f(x))=x</math>.
| |
| − | | |
| − | So we have: <math>\frac{a(\frac{ax+b}{cx+d})+b}{c(\frac{ax+b}{cx+d})+d} = x \Rightarrow x^2(ac+cd)+x(d^2-a^2)-(ab+bd)=0</math>
| |
| − | | |
| − | Thus we require:
| |
| − | | |
| − | <math>ac+cd = 0 \rightarrow c=0</math> or <math>a = -d</math>
| |
| | | | |
| − | <math>d^2-a^2 = 0 \rightarrow a = d</math> or <math>a = -d</math> | + | and thus the answer is <math>\boxed{\textbf{(B) }338551}</math>. |
| | | | |
| − | <math>ab+bd = 0 \rightarrow b=0</math> or <math>a = -d</math>
| + | ~[https://artofproblemsolving.com/wiki/index.php/User:Reda_mandymath reda_mandymath] |
| | | | |
| − | Note that if <math>a = -d</math> then all 3 cases work and give <math>11^3=1331</math> solutions.
| + | ==Solution 3 (lazy + quick)== |
| | | | |
| − | If instead <math>c=0</math> and <math>a \neq -d</math> then we require <math>a=d</math> and <math>b=0</math> which then give <math>10</math> solutions.
| + | We'll first try to isolate <math>a_n</math> in terms of <math>a_{n-1}</math>. |
| | | | |
| − | Now, we must remove all extraneous cases. This is when <math>x(ac+cd)+bc+d^2 = 0</math> (note this includes the case where <math>c=d=0</math>).
| + | <math>(a_n-1)(n-1+1)=(n-1)(a_{n-1}+1)</math> |
| | | | |
| − | So this is equivalent to having both <math>ac+cd = 0</math> and <math>bc + d^2 = 0.</math>
| + | <math>a_n-1=\frac{(n-1)(a_{n-1}+1)}{n}</math> |
| | | | |
| − | If <math>c = d = 0</math> we have <math>11</math> solutions.
| + | <math>a_n=\frac{n-1}{n}(a_{n-1}+1)+1</math> |
| | | | |
| − | If <math>c = 0</math> and <math>d \neq 0</math> then we have <math>0</math> solutions.
| + | <math>a_n=\frac{n-1}{n}(a_{n-1})+\frac{n-1}{n}+1</math> |
| | | | |
| − | If <math>c \neq 0</math> and <math>d = 0</math> then we require <math>a=0</math> and <math>b=0</math> so we have <math>10</math> solutions.
| + | <math>a_n=\frac{n-1}{n}(a_{n-1})+\frac{2n-1}{n}</math> |
| | | | |
| − | And if <math>c \neq 0</math> and <math>d \neq 0</math> we have <math>a = -d</math> and <math>d^2 = -bc</math>, see that if <math>\left|d\right|=1,3,4,5</math> we have <math>2</math> solutions and if <math>\left|d\right|=2</math> we have <math>6</math> solutions, so a total of <math>2(2+6+2+2+2) = 28</math> solutions.
| + | Now, as with many, many of these large summation problems, if we just evaluate the first few values in the series, a pattern should emerge quickly. Here it works out well since our product on the LHS cancels out. |
| | | | |
| − | Thus, the final answer is <math>1331+10-11-10-28 =\boxed{\textbf{(B) }1292}</math>
| + | <math>a_1=2</math> |
| | | | |
| − | ~LuisFonseca123
| + | <math>a_2=\frac{1}{2}(2)+\frac{3}{2}=\frac{5}{2}</math> |
| | | | |
| | + | <math>a_3=\frac{2}{3}(\frac{5}{2})+\frac{5}{3}=\frac{10}{3}</math> |
| | | | |
| − | == Solution 5 == | + | <math>a_4=\frac{3}{4}(\frac{10}{3})+\frac{7}{4}=\frac{17}{4}</math> |
| | | | |
| − | Proceed the same way as the other solutions keeping in mind that <math>{y = y^{-1}}</math>. Then, I got:
| + | Here it becomes glaringly obvious that <math>a_n=\frac{n^2+1}{n}=n+\frac{1}{n}</math>. |
| − | <math>\frac{(b - dx)}{(cx - a)} = \frac{(ax + b)}{(cx + d)}</math>. Cross multiplying and matching coefficients, we get:
| |
| − | <math>{-cd(x^{2})}</math> = <math>{ac(x^{2})}</math>; <math>{bd}</math> = <math>{-ab}</math>; and <math>{-x(d^{2})}</math> = <math>{-x(a^{2})}</math>. Then, I broke it up into 4 cases:
| |
| | | | |
| − | Case 1: <math>{b \neq 0}</math>, <math>{c = 0}</math>, <math>{a = -d}</math>.
| + | So, <math>a_n^2=n^2+\frac{1}{n^2}+2</math>. |
| | | | |
| − | Case 2: <math>{b = 0}</math>, <math>{c = 0}</math>, <math>{a^{2} = d^{2}}</math>.
| + | We proceed with the same summation strategy as Solution 1 and get our answer of <math>\boxed{\textbf{(B) }338551}</math>. |
| | | | |
| − | Case 3: <math>{b \neq 0}</math>, <math>{c \neq 0}</math>, <math>{a = -d}</math>.
| + | *Note: You only have find the answer's units digit from the answer choices; that's <math>0+1+0</math> for each sum, giving choice B. |
| | | | |
| − | Case 4: <math>{b = 0}</math>, <math>{c \neq 0}</math>, <math>{a = -d}</math>.
| + | ~nm1728 |
| | | | |
| − | I first accounted the total number of cases for everything to work WITHOUT any restrictions. So for Case 1, there would be 10 possibilities for <math>{b}</math> and 11 for the part where <math>{a = -d}</math>. So a total of 110 cases. Similarly, in the same fashion, Case 2 would yield 21 cases. Case 3 would yield 1100 cases and Case 4 would bring a total of 110 cases. So, our total possibilities right now is <math>{110 + 21 + 1100 + 110}</math> = <math>{1341}</math>. But wait! Notice a lot of these cases would bring the denominator of <math>{y}</math> to be 0 namely <math>{cx + d}</math> to be 0. We don't want this! So we have to subtract out all the cases that bring <math>{cx + d}</math> to be 0. Notice for Case 1, <math>{c = 0}</math> so if <math>{d = 0}</math>, we have a bad case. We shall keep track of all the "bad" cases. For Case 1, any quadruple that includes <math>{d = 0}</math> is "bad". So no restrictions upon <math>{b}</math> since <math>{a}</math> depends upon <math>{d}</math>. Therefore, we have 10 bad cases so far remember, <math>{b \neq 0}</math> for Case 1.
| + | ==Solution 4 (transform)== |
| | | | |
| − | We now proceed to Case 2. Notice we only have 1 "bad" case namely <math>{a = 0}</math>. This is because <math>{a}</math> and <math>{d}</math> depend on each other again.
| + | <cmath>n a_{n} - n = (n-1) a_{n-1} + n-1 </cmath> |
| | + | <cmath>n \cdot a_{n} - n^2 = (n-1) a_{n-1} - n^2 +2n-1 </cmath> |
| | + | <cmath>n \cdot a_{n} - n^2 = (n-1) a_{n-1} - (n-1)^2 </cmath> |
| | + | Set <cmath> b_{n} = n a_{n} - n^2 </cmath> |
| | + | <cmath>n a_{n} - n^2 = b_{n} = b_{n-1}= ... = b_{1} =1 </cmath> |
| | + | <cmath> a_{n} = \frac{1}{n} + n </cmath> |
| | + | <cmath> a_{n}^2 = \frac{1}{n^2} + n^2 +2 </cmath> |
| | | | |
| − | Now Case 3. This will have quite a bit of "bad" cases as <math>{c \neq 0}</math>. Firstly, clearly <math>{a = 0}</math> would again have some overcounting going on so we would have to subtract out 10 again as the value of <math>{b}</math> doesn't matter. Then, we start off with <math>{c = -5}</math>. Obviously, then <math>{d = 5}</math> would yield a bad case IF <math>{x = 1}</math>. Now we see what happens is <math>{x = 2}</math>. Then, the denominator would be <math>{2c + d}</math>. For this to be 0, <math>{2c = -d}</math>. So all even values of <math>{d}</math> would be considered "bad". Thus, we would have <math>{d = -2, -4, 2, 4}</math> to be "bad" cases which yields a subtotal of 4 cases. Now, the same thing would happen if <math>{x = 3}</math> except all multiples of 3 would be considered "bad". So <math>{d = -3, 3}</math> would be "bad" or a subtotal of 2 cases. Then, we see the pattern. Multiples of 4 could also be eliminated for <math>{x = 4}</math> which would yield <math>{d = -4, 4}</math> but these overcount the multiples of 2 so no need to worry about them. Lastly, multiples of 5 wouldn't work if <math>{x = 5}</math> so <math>{d = -5, 5}</math> is "bad" or 2 cases. Then, <math>{d = -1, 1}</math> could also be eliminated. Then, at last <math>{d = 0}</math> would also not work. Finally, a total of <math>{10 + 4 + 2 + 2 + 1}</math> cases would be "bad" which yields a subtotal of 19 cases. As you would see, Case 4 has the exact same restrictions on <math>{c}</math> but not <math>{b}</math>. So we can predict it would yield the same number of "bad" cases as Case 3. Finally, we could add up all of the "bad" cases we have:
| + | <cmath> Sum = 1^2 + 2^2 + ... + 100^2 + 2* 100 + 1^2 + 1 / 2^2 + ... + 1/ 100^2 = 100 * 101 *201 / 6 + 200 + 1 + ... = 338551.xxx \boxed{\textbf{(B) }338551} </cmath> |
| − | <math>{10 + 1 + 19 + 19}</math> = <math>{49}</math> "bad" cases. What we did here is also known as counting up all the "asymptotes".
| |
| | | | |
| − | Our answer should be <math>{1341 - 49 = 1292}</math> or <math>\boxed{\textbf{(B) } 1292}</math>.
| + | ~[https://artofproblemsolving.com/wiki/index.php/User:Cyantist luckuso] |
| | | | |
| − | ~ilikemath247365
| + | ==Solution 5 (transform)== |
| | | | |
| − | ==Cases==
| + | According to the equation given, |
| | | | |
| − | Case 1: <math>d=-a\land c\neq0</math>, <math>10\times11\times11=1210</math> possibilities
| + | <cmath>\frac{a_n - 1}{n - 1} = \frac{a_{n - 1} + 1}{n}</cmath> |
| | | | |
| − | Excluded from Case 1: <math>d=-a\land c\neq0\land d^{2}=-bc</math>, <math>10+4+12+4+4+4=38</math> possibilities
| + | <cmath>na_n = (n - 1)a_{n - 1} + 2n - 1 = (n - 2)a_{n - 2} + (2n-3) + (2n - 1) = 1*a_{1} + 1 + 3 + ... + 2n - 1 = 1 + \frac{1+ (2n-1)*n}{2} = n^2+ 1 </cmath> |
| | | | |
| − | Case 2: <math>d=-a\land c=0\land d\neq0</math>, <math>10\times11=110</math> possibilities
| + | <cmath>a_n =n + \frac{1}{n}</cmath> |
| | | | |
| − | Case 3: <math>d=a\land c=0\land d\neq0\land b=0</math>, <math>10=10</math> possibilities
| + | The rest continues similar to Solution 1 or 2 |
| | | | |
| − | Answer: <math>1210-38+110+10=1292</math>
| + | ~[https://artofproblemsolving.com/wiki/index.php/User:Cyantist luckuso] |
| | | | |
| | ==See also== | | ==See also== |
| | {{AMC12 box|year=2024|ab=A|num-b=20|num-a=22}} | | {{AMC12 box|year=2024|ab=A|num-b=20|num-a=22}} |
| | {{MAA Notice}} | | {{MAA Notice}} |
and the sequence 
satisfies the recurrence relation ![\[\frac{a_n -1}{n-1}=\frac{a_{n-1}+1}{(n-1)+1}\]](http://latex.artofproblemsolving.com/a/8/3/a83f618893faee660d62f76743a90ecfbecf74f2.png)
for all 
What is the greatest integer less than or equal to ![\[\sum^{100}_{n=1} a_n^2?\]](http://latex.artofproblemsolving.com/0/f/3/0f327ec398b8186c05df6471bbecad3dbce2e296.png)
.
. Then the previous relation becomes
![\[b_n=b_{n-1}+2(n-1)\]](http://latex.artofproblemsolving.com/c/5/a/c5a7e95be5c30ddfb2f4f762b0db2bd1a4734953.png)
until 
and use telescoping to derive an explicit formula:
![\[b_{n-1}=b_{n-2}+2(n-2)\]](http://latex.artofproblemsolving.com/b/6/a/b6ad06f40da56674b5586286a666c839564d62ee.png)
![\[b_{n-2}=b_{n-3}+2(n-3)\]](http://latex.artofproblemsolving.com/7/8/3/7839c84a48dd6a0eb87516ba0be3bbf386ec4b40.png)
![\[\cdot\]](http://latex.artofproblemsolving.com/d/9/4/d9487ddabbfc1d9f8c40b90fa7f18dacb3ea8588.png)
![\[b_2=b_1+2(1)\]](http://latex.artofproblemsolving.com/8/0/d/80dc61fa289867b34609797cd71c4daa08235074.png)
![\[b_n+b_{n-1}+\cdots+b_2=b_{n-1}+b_{n-2}+\cdots+b_1+2((n-1)+(n-2)+\cdots+1)\]](http://latex.artofproblemsolving.com/d/3/c/d3ce7b6366e039c723b7787e3bfcac2c183a7c2d.png)
![\[b_n-b_1=2\cdot\frac{n(n-1)}{2}\]](http://latex.artofproblemsolving.com/2/3/1/23164ea6bc39a0f8b3f30cdc84f2521652a76221.png)
![\[b_n-1=n(n-1)\]](http://latex.artofproblemsolving.com/8/2/a/82ae8cb6c90297fd19e449fcb478ffd98679b268.png)
![\[b_n=n(n-1)+1\]](http://latex.artofproblemsolving.com/2/7/1/2719310275bc8a06056ea8c56e2e1d55d2ad84c7.png)
back into our equation:
![\[n(a_n-1)=n(n-1)+1\]](http://latex.artofproblemsolving.com/5/2/8/5287d043c10a955f6734f8c00f2adca93658609f.png)
![\[a_n-1=n-1+\frac{1}{n}\]](http://latex.artofproblemsolving.com/1/4/8/1486942351390038e6a87943645804a0067631b7.png)
![\[a_n=n+\frac{1}{n}\]](http://latex.artofproblemsolving.com/d/7/0/d7084b2463d539e4b227f3f86f6cac2d107619dd.png)
![\[a_n^2=n^2+\frac{1}{n^2}+2\]](http://latex.artofproblemsolving.com/a/1/c/a1cec7d58b59bd35fd10fc2e23b166c972991dcf.png)
![\[\sum^{100}_{n=1} a_n^2= \sum^{100}_{n=1} n^2+ \sum^{100}_{n=1} \frac{1}{n^2}+ \sum^{100}_{n=1} 2\]](http://latex.artofproblemsolving.com/d/6/6/d668848f5130b2ec363624ee40a68061bfbaf104.png)
, and we also know that 
, so the requested sum is equivalent to 
. All that remains is to calculate 
, and we know that this value lies between 
(see the note below for a proof). Thus,
![\[\sum^{100}_{n=1} a_n^2= \sum^{100}_{n=1} \frac{1}{n^2}+338550<2+338550=338552\]](http://latex.artofproblemsolving.com/5/0/1/501ab41243caf8df3a35c22bf04aefedbab8ec51.png)
![\[\sum^{100}_{n=1} a_n^2= \sum^{100}_{n=1} \frac{1}{n^2}+338550>1+338550=338551\]](http://latex.artofproblemsolving.com/0/2/4/0246b54f2afff825907847e7f4a2cf93fdda06cd.png)
![\[\sum^{100}_{n=1} a_n^2\in(338551,338552)\]](http://latex.artofproblemsolving.com/0/d/0/0d0d7ef40a93340e07bde5ecb6cf956b7d178e69.png)
.
. It is obvious that the sum is greater than 1 (since it contains 
as one of its terms).
![\[\sum^{100}_{n=1} \frac{1}{n^2}<\sum^{\infty}_{n=1} \frac{1}{n^2}=\frac{1}{1^1}+\left(\frac{1}{2^2}+\frac{1}{3^2}\right)+\left(\frac{1}{4^2}+\frac{1}{5^2}+\frac{1}{6^2}+\frac{1}{7^2}\right)+\cdots\]](http://latex.artofproblemsolving.com/8/1/4/81435353c7d2b1372761741443e4cc6b08d089e0.png)
![\[<1+\left(\frac{1}{2^2}+\frac{1}{2^2}\right)+\left(\frac{1}{4^2}+\frac{1}{4^2}+\frac{1}{4^2}+\frac{1}{4^2}\right)+\left(\frac{1}{8^2}+\frac{1}{8^2}+\frac{1}{8^2}+\frac{1}{8^2}+\frac{1}{8^2}+\frac{1}{8^2}+\frac{1}{8^2}+\frac{1}{8^2}\right)+\cdots\]](http://latex.artofproblemsolving.com/f/9/b/f9b65f5fa13dbacce513c7ae32a3905ed926830f.png)
![\[=1+\frac{2}{2^2}+\frac{4}{4^2}+\frac{8}{8^2}+\cdots\]](http://latex.artofproblemsolving.com/2/6/e/26e12e00a8494410dc30c71130fcafdcc0fb2b32.png)
![\[=1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots=2\]](http://latex.artofproblemsolving.com/d/f/a/dfa6775e1d244e52eaa57a04d1e8b70b2bd99a75.png)
. ~eevee9406
![\[\frac{a_n - 1}{n - 1} = \frac{a_{n - 1} + 1}{n}\]](http://latex.artofproblemsolving.com/2/d/5/2d5c2cae3db389c4dab217e1c753dc7708b76e4f.png)
![\[na_n - n = (n - 1)a_{n - 1} + n - 1\]](http://latex.artofproblemsolving.com/b/f/f/bff02b206365512679adb2cb3a8506910c41164d.png)
![\[na_n - (n - 1)a_{n - 1} = 2n - 1\]](http://latex.artofproblemsolving.com/0/c/5/0c5ebc891d3e055a41825ffaa4d362fc209199e8.png)
, 
, then 
, where 
, then we obtain that
![\[b_n = b_1 + (b_2 - b_1) + (b_3 - b_2) + \cdots + (b_n - b_{n - 1})\]](http://latex.artofproblemsolving.com/a/7/3/a7319e3904dcaff1e1e03a596d11cf787004c43a.png)
![\[b_n = 2 + 3 + 5 + \cdots + (2n - 1) = 1 + n^2\]](http://latex.artofproblemsolving.com/b/b/8/bb82ecb1f564dc116c05d3b06845e00dfe61ea09.png)
![\[a_n = \frac{1 + n^2}{n} = n + \frac{1}{n}\]](http://latex.artofproblemsolving.com/f/5/1/f512593c5d30033c05ee7824b65edc156082b01e.png)
![\[\sum_{n = 1}^{100}\frac{1}{n^2} = 1 + \sum_{n = 2}^{100}\frac{1}{n^2} > 1\]](http://latex.artofproblemsolving.com/e/2/e/e2ee67e667d2369d8a143bd3b55422f1dbad4fac.png)
![\[\sum_{n = 1}^{100}\frac{1}{n^2} < 1 + \sum_{n = 2}^{100}\frac{1}{n(n - 1)} = 1 + 1 - \frac{1}{100} < 2~~(\text{telescope})\]](http://latex.artofproblemsolving.com/9/a/2/9a20f32240185685ca324e2f1de8cf04ae094a6b.png)
.
.
.
for each sum, giving choice B.
for each sum, giving choice B.![\[n a_{n} - n = (n-1) a_{n-1} + n-1\]](http://latex.artofproblemsolving.com/b/9/8/b982aaab7536628ac5b5903b0ceac08fa7259658.png)
![\[n \cdot a_{n} - n^2 = (n-1) a_{n-1} - n^2 +2n-1\]](http://latex.artofproblemsolving.com/8/0/3/8039373c1820de20348592399225e0d1173e8eea.png)
![\[n \cdot a_{n} - n^2 = (n-1) a_{n-1} - (n-1)^2\]](http://latex.artofproblemsolving.com/5/0/7/5075288fd1fe05a3cfff615218d0194de0dba8e1.png)
Set ![\[b_{n} = n a_{n} - n^2\]](http://latex.artofproblemsolving.com/5/8/1/58130f98a38c59b552b6e537d7b8f3f742d6b010.png)
![\[n a_{n} - n^2 = b_{n} = b_{n-1}= ... = b_{1} =1\]](http://latex.artofproblemsolving.com/e/d/2/ed290634a64c66117ee504cb5130d9e08de15a47.png)
![\[a_{n} = \frac{1}{n} + n\]](http://latex.artofproblemsolving.com/c/a/d/cadf4c5240ec0cfbc5f90f49db419ec664dcfaeb.png)
![\[a_{n}^2 = \frac{1}{n^2} + n^2 +2\]](http://latex.artofproblemsolving.com/e/8/0/e800606d9932839d18cb62606559ddc47e60a621.png)
![\[Sum = 1^2 + 2^2 + ... + 100^2 + 2* 100 + 1^2 + 1 / 2^2 + ... + 1/ 100^2 = 100 * 101 *201 / 6 + 200 + 1 + ... = 338551.xxx \boxed{\textbf{(B) }338551}\]](http://latex.artofproblemsolving.com/5/9/e/59e00ec10ca6bee3377d5ac1c0fe9e0ef701bf30.png)
![\[na_n = (n - 1)a_{n - 1} + 2n - 1 = (n - 2)a_{n - 2} + (2n-3) + (2n - 1) = 1*a_{1} + 1 + 3 + ... + 2n - 1 = 1 + \frac{1+ (2n-1)*n}{2} = n^2+ 1\]](http://latex.artofproblemsolving.com/3/1/1/311ed4e78463aaddeaac4dedb8e60fcea461539c.png)
![\[a_n =n + \frac{1}{n}\]](http://latex.artofproblemsolving.com/9/3/2/9324777c39a1730fbc248ad7ca73330d27f3e155.png)
