Difference between revisions of "2002 AMC 12P Problems/Problem 11"
The 76923th (talk | contribs) m (→Solution) |
(→Solution 2 (Cheese)) |
||
(25 intermediate revisions by 2 users not shown) | |||
Line 16: | Line 16: | ||
</math> | </math> | ||
− | == Solution == | + | == Solution 1 == |
− | We may write <math>\frac{1}{t_n}</math> as <math>\frac{2}{n(n+1)}</math> | + | We may write <math>\frac{1}{t_n}</math> as <math>\frac{2}{n(n+1)}</math> and do a partial fraction decomposition. |
+ | Assume <math>\frac{2}{n(n+1)} = \frac{A_1}{n} + \frac{A_2}{n+1}</math>. | ||
+ | |||
+ | Multiplying both sides by <math>n(n+1)</math> gives <math>2 = A_1(n+1) + A_2(n) = (A_1 + A_2)n + A_1</math>. | ||
+ | |||
+ | Equating coefficients gives <math>A_1 = 2</math> and <math>A_1 + A_2 = 0</math>, so <math>A_2 = -2</math>. Therefore, <math>\frac{2}{n(n+1)} = \frac{2}{n} - \frac{2}{n+1}</math>. | ||
+ | |||
+ | Now <math>\frac{1}{t_1} + \frac{1}{t_2} + ... + \frac{1}{t_{2002}} = 2((\frac{1}{1} - \frac{1}{2}) + (\frac{1}{2} - \frac{1}{3}) + ... + (\frac{1}{2002} - \frac{1}{2003})) = 2(1 - \frac{1}{2003}) = \boxed{\textbf{(C) } \frac{4004}{2003}}.</math> | ||
+ | |||
+ | Note: For the sake of completeness, I put the full derivation of the partial fraction decomposition of <math>\frac{2}{n(n+1)}</math> here. However, on the contest, the decomposition step would be much faster since it is so well-known. | ||
+ | |||
+ | == Solution 2 (Cheese) == | ||
+ | As with all telescoping problems, there is a solution that involves induction. In competition, it is sufficient to conjecture the formula but not prove it. For sake of completeness and practice, we will prove the formula for <math>\sum_{i=1}^{n} \frac{1}{t_n}.</math> | ||
+ | |||
+ | With some guess and check: | ||
+ | |||
+ | <math>n=1</math> | ||
+ | |||
+ | \begin{align*} | ||
+ | \frac{1}{t_1}&=\frac{2}{1(2)} \\ | ||
+ | &=\frac{2}{2} \\ | ||
+ | \end{align*} | ||
+ | |||
+ | <math>n=2</math> | ||
+ | |||
+ | \begin{align*} | ||
+ | \frac{1}{t_1}+\frac{1}{t_2}&=\frac{2}{2}+\frac{2}{2(3)} \\ | ||
+ | &=\frac{4}{3} \\ | ||
+ | \end{align*} | ||
+ | |||
+ | <math>n=3</math> | ||
+ | |||
+ | \begin{align*} | ||
+ | \frac{1}{t_1}+\frac{1}{t_2}+\frac{1}{t_3}&=\frac{4}{3}+\frac{2}{3(4)} \\ | ||
+ | =\frac{6}{4} \\ | ||
+ | \end{align*} | ||
+ | |||
+ | From <math>\frac{2}{2}, \frac{4}{3},</math> and <math>\frac{6}{4},</math> we can conjecture <math>\sum_{i=1}^{n} \frac{1}{t_n} = \frac{2n}{n+1}.</math> A quick check shows that for <math>n=4</math> gives <math>\frac{8}{5},</math> which means our inductive hypothesis is most likely correct. Thus, our answer is <math>\sum_{i=1}^{2002} \frac{1}{t_n} = \frac{2(2002)}{2002+1}=\boxed{\textbf{(C) } \frac{4004}{2003}}.</math> | ||
+ | |||
+ | We will prove this with induction for all <math>n \geq 1</math> as promised. | ||
+ | |||
+ | Base case: <math>n=1.</math> | ||
+ | |||
+ | \begin{align*} | ||
+ | \sum_{i=1}^{1} \frac{1}{t_n}&=\frac{1}{t_n} \\ | ||
+ | &=\frac{2}{1(2)} \\ | ||
+ | &=1 \\ | ||
+ | &=\frac{2(1)}{1+1} \\ | ||
+ | &=1 \\ | ||
+ | \end{align*} | ||
+ | |||
+ | Since <math>1=1,</math> the base case is proven. | ||
+ | |||
+ | Induction step: <math>n=k+1.</math> | ||
+ | |||
+ | Assume: <math>n=k</math> <math>\implies</math> <math>\sum_{i=1}^{k} \frac{1}{t_k} = \frac{2k}{k+1}.</math> | ||
+ | |||
+ | We want to prove: <math>n=k+1</math> <math>\implies</math> <math>\sum_{i=1}^{k+1} \frac{1}{t_k} = \frac{2(k+1)}{k+2}.</math> | ||
+ | |||
+ | We are given <math>\sum_{i=1}^{k} \frac{1}{t_k} = \frac{2k}{k+1}.</math> Add <math>\frac{1}{t_{k+1}}</math> on both sides and simplify. | ||
+ | |||
+ | \begin{align*} | ||
+ | \sum_{i=1}^{k} \frac{1}{t_k} + \frac{1}{t_{k+1}} &= \frac{2k}{k+1} + \frac{1}{t_{k+1}} \\ | ||
+ | \sum_{i=1}^{k+1} \frac{1}{t_k} &= \frac{2k}{k+1} + \frac{2}{(k+1)(k+2)} \\ | ||
+ | \sum_{i=1}^{k+1} \frac{1}{t_k} &= \frac{2k(k+2)}{(k+1)(k+2)} + \frac{2}{(k+1)(k+2)} \\ | ||
+ | \sum_{i=1}^{k+1} \frac{1}{t_k} &= \frac{2k(k+2)+2}{(k+1)(k+2)} \\ | ||
+ | \sum_{i=1}^{k+1} \frac{1}{t_k} &= \frac{2k^2+4k+2}{(k+1)(k+2)} \\ | ||
+ | \sum_{i=1}^{k+1} \frac{1}{t_k} &= \frac{2(k+1)^2}{(k+1)(k+2)} \\ | ||
+ | \sum_{i=1}^{k+1} \frac{1}{t_k} &= \frac{2(k+1)}{(k+2)} \\ | ||
+ | \end{align*} | ||
+ | |||
+ | Given the inductive hypothesis, we have proven the induction step. Thus, we have completed our proof for induction. | ||
== See also == | == See also == | ||
{{AMC12 box|year=2002|ab=P|num-b=10|num-a=12}} | {{AMC12 box|year=2002|ab=P|num-b=10|num-a=12}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 10:05, 15 July 2024
Problem
Let be the
th triangular number. Find
Solution 1
We may write as
and do a partial fraction decomposition.
Assume
.
Multiplying both sides by gives
.
Equating coefficients gives and
, so
. Therefore,
.
Now
Note: For the sake of completeness, I put the full derivation of the partial fraction decomposition of here. However, on the contest, the decomposition step would be much faster since it is so well-known.
Solution 2 (Cheese)
As with all telescoping problems, there is a solution that involves induction. In competition, it is sufficient to conjecture the formula but not prove it. For sake of completeness and practice, we will prove the formula for
With some guess and check:
\begin{align*} \frac{1}{t_1}&=\frac{2}{1(2)} \\ &=\frac{2}{2} \\ \end{align*}
\begin{align*} \frac{1}{t_1}+\frac{1}{t_2}&=\frac{2}{2}+\frac{2}{2(3)} \\ &=\frac{4}{3} \\ \end{align*}
\begin{align*} \frac{1}{t_1}+\frac{1}{t_2}+\frac{1}{t_3}&=\frac{4}{3}+\frac{2}{3(4)} \\ =\frac{6}{4} \\ \end{align*}
From and
we can conjecture
A quick check shows that for
gives
which means our inductive hypothesis is most likely correct. Thus, our answer is
We will prove this with induction for all as promised.
Base case:
\begin{align*} \sum_{i=1}^{1} \frac{1}{t_n}&=\frac{1}{t_n} \\ &=\frac{2}{1(2)} \\ &=1 \\ &=\frac{2(1)}{1+1} \\ &=1 \\ \end{align*}
Since the base case is proven.
Induction step:
Assume:
We want to prove:
We are given Add
on both sides and simplify.
\begin{align*} \sum_{i=1}^{k} \frac{1}{t_k} + \frac{1}{t_{k+1}} &= \frac{2k}{k+1} + \frac{1}{t_{k+1}} \\ \sum_{i=1}^{k+1} \frac{1}{t_k} &= \frac{2k}{k+1} + \frac{2}{(k+1)(k+2)} \\ \sum_{i=1}^{k+1} \frac{1}{t_k} &= \frac{2k(k+2)}{(k+1)(k+2)} + \frac{2}{(k+1)(k+2)} \\ \sum_{i=1}^{k+1} \frac{1}{t_k} &= \frac{2k(k+2)+2}{(k+1)(k+2)} \\ \sum_{i=1}^{k+1} \frac{1}{t_k} &= \frac{2k^2+4k+2}{(k+1)(k+2)} \\ \sum_{i=1}^{k+1} \frac{1}{t_k} &= \frac{2(k+1)^2}{(k+1)(k+2)} \\ \sum_{i=1}^{k+1} \frac{1}{t_k} &= \frac{2(k+1)}{(k+2)} \\ \end{align*}
Given the inductive hypothesis, we have proven the induction step. Thus, we have completed our proof for induction.
See also
2002 AMC 12P (Problems • Answer Key • Resources) | |
Preceded by Problem 10 |
Followed by Problem 12 |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | |
All AMC 12 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.