AIME: A Pattern in Determinants (2011 II Problem 11)

Share
Embed
• Published on Aug 11, 2018
• We construct matrices whose determinants follow an interesting pattern.
Your support is truly a huge encouragement.
Every subscriber and every like are wholeheartedly appreciated.

• Ljubeta Bulatovic 3 months ago

All is okay!

• Debraj Banerjee 10 months ago

What will be the answer if all 3s are replaced by sqrt(a-1) and 10s by a ?

• Hung Hin Sun 10 months ago

That means you want to generalize the problem. We can use the method of different equations. Consider the equation x^2=ax-(a-1), the roots are 1 and (a-1), so the solution of Dn is A+B*(a-1)^n. We use D1=a and D2=a^2-a+1 to solve for A and B. It can be found that A=-1/(a-2) and B=(a-1)/(a-2) for a not equal to 1 and 2. Then Dn = [(a-1)^(n+1)-1]/(a-2). The general term in the infinite sum should be modified to 1/[(a-2)Dn+1], which is equal to 1/[(a-1)^(n+1)]. Therefore the infinite sum is [1/(a-1)^2]/[1-1/(a-1)]=1/[(a-1)(a-2)]. Then the final answer will be a^2-3a+3.

• Hung Hin Sun 10 months ago

For the recurrence relation, we can solve it by using difference equation, that is to consider x^2=10x-9, the roots are 1 and 9, so the solution for the sequence Dn is of the form A+B*9^n. We use D1and D2 to determine A and B. We can find out A=-1/8, B=9/8, so we have Dn=[9^(n+1)-1]/8. Therefore, 8Dn+1=9^(n+1) and the infinite sum is (1/81)/(1-1/9)=1/72.

• EmissaryOfSmeagol 10 months ago +1

Aren't geometric series normally introduced during the third term or second semester of Calculus (Series Calculus)? You mentioned AIME problems do not require Calculus and yet the a/(1-r) concept is a Calculus concept.

• @EmissaryOfSmeagol Not only precalculus, I believe I was taught this in algebra 1 albeit the trash stupid curriculum has made it so it is fed to us, with no explanation. Sadly no teachers bother to actually explain anything anymore because they don't get payed extra to do so.

• EmissaryOfSmeagol 10 months ago +1

This is very interesting, as I never saw the formula until college level. My precalculus class covered sequences and trig (no limits, series, etc and I did study in the US).
Maybe my school wasn't very advanced in curriculum. I don't doubt you guys, I am just surprised to hear that many of you got introduced to the subjects quite early!

• Kevin Tong 10 months ago

The proof of the geometric series formula doesn't require calculus. I've never seen the geometric series pop up in calculus except for testing convergence and divergence of a series. It's almost not related at all to calculus aside from the idea of a limit, which is precalculus (in America).
Anyway, the proof is fairly simple. Assume you the series is
S=a+ar+ar^2+ar^3+...+ar^n
Then multiply by r to get
Sr=ar+ar^2+ar^3+...+ar^(n+1)
now subtract the two equation to get
S-Sr=S(1-r)=a-ar^(n+1)=a(1-r^(n+1))
S=a(1-r^(n+1))/(1-r)
which is the formula for finite geometric series. When you go to infinite, you simply take the limit as n approaches infinity, in which r^(n+1) gets closer to 0 since |r|

• EmissaryOfSmeagol 10 months ago +1

LetsSolveMathProblems interesting. I've done math in the US and I never saw the formula until Series Calc.

• LetsSolveMathProblems  10 months ago +1

The rigorous proof of infinite geometric series formula does require calculus, and the formal proof is usually given in Calculus II or Real Analysis in college. However, the formula itself is often informally introduced at a high school level. In the United States, the students usually learn the formula in Pre-Calculus class.

• LSMP,
I have a challenge for you
(2x-1)^20-(ax+b)^20=(x^2 + px + q)^10? . find all real numbers a , b ,p ,q so that the identity true for all x values

• Kevin Tong 10 months ago +1

The leading coefficient of the RHS is clearly 1, while the leading coefficient on the LHS is clearly 2^20 - a^20, so a=20th root of 2^20-1 for the equation to hold.
Next, the constant term on the LHS is 1-b^20, while it is q^10 on the RHS, so we must have b^20+q^10=1.
I'll think about the p equation later.

• Will Bishop 10 months ago

I had the formula D_n = 10D_(n-1) + 9D_(n-2) but took a while to realize that D_n = 1 + 9 + 9^2 + ... + 9^n. Once you get that, everything follows so nicely!

• Electro Wizard 10 months ago

Sir plz bring a video on A question related to recurrence relation

• Electro Wizard 10 months ago +1

Can we solve this question using recurrence relation instead of mathematical induction?

• Hung Hin Sun 10 months ago +1

For the recurrence relation, we can solve it by using difference equation, that is to consider x^2=10x-9, the roots are 1 and 9, so the solution for the sequence Dn is of the form A+B*9^n. We use D1and D2 to determine A and B. We can find out A=-1/8, B=9/8, so we have Dn=[9^(n+1)-1]/8. Therefore, 8Dn+1=9^(n+1) and the infinite sum is (1/81)/(1-1/9)=1/72.

• Hung Hin Sun 10 months ago

we can solve it by method of difference equations.

• Crazy Phil 10 months ago

• Kevin Tong 10 months ago +4

I remember doing this and thinking what in the world is going on, but I was still able to solve it by noticing that geometric series, although I never proved it. Just wondering, is there a more concrete Linear Algebra method to proving this?

• Kevin Tong 10 months ago +1

Jonathan Liu Oh wow, that's interesting!! 😂 It is a fairly large community into math and computer science. And wow, gold division in USACO?!?!? That's super good! I haven't competed in USACO before, but I'm just aiming for platinum this year. Hope you make IOI!! Anyway, my Summer's been quite interesting, sad to hear yours was mundane. I went on a 2 week cruise around the Baltic at the beginning, and spent much of the rest studying for the USAMO and IMO. The only boring stuff was summer hw and studying for the SAT 😐 my test is on the 25th. Sadly school has started for me yesterday and now I'm drowning in hw again 😭 hope to get to know you more!!

• Jonathan Liu 10 months ago +1

Kevin, I've seen you everywhere: in the comments section of coding, college application, and math competition videos. It's profoundly astonishing how our interests overlap. Both of us alike are rising juniors and possess the proficiency of condescension, actively instigating our computer science teachers. As for me personally, my AMC and AIME experience has been a rough one, barely missing qualification in eighth and ninth grade and scoring a meager 4 on the AIME this year. In addition, I've participated in the USACO, gold division. Constructing algorithms, however, instantly brings me to tears, halting any possible future progress. Anyhow, my summer has been quite mundane, how has yours been?

• Allan Lago 10 months ago

Oh wow, I found that D_n = 10*D_n-1 - 9*D_n-2 almost instantly but failed to notice the geometric sequence for the first three ns.

• Frank Steffahn 10 months ago

Even though it is not presented as such in this video, IMO finding that conjecture that it’s a geometric series with factor 1/9 is by far the hardest part of the exercise. In the video he only mastered it effortlessly because (1) he already solved the exercise beforehand and (2) he knew from context that the series couldn’t really be anything but geometric for the exercise to make sense.
I had the same problem like you did but found a more complicated way of finding the right conjectures:
I (for whatever reason) explored what D_n looks like represented not by D_n-1 and D_n-2 but also by the pairs D_n-2,D_n-3 or D_n-3,D_n-4 etc.
that’s D_n = 91D_n-2 - 90D_n-3
and D_n = 820 D_n-3 - 819D_n-4
and noticed values of the D-sequence reappearing in the coefficients.
Especially the right coefficients always were D_i values decreased by 1. But the way they appeared there (when multiplying out the D_n = 10(D_n-1) - 9D_n-2 = 10(10D_n-2 - 9D_n-3) - 9D_n-2 = ...
way always by means of 9 times another D-value.
(In general: D_n = a*D_n-i + b*D_n-i-1 = a*(10*D_n-i-1 - 9*D_n-i-2) - b*D_n-i-1 = ...*D_n-i-1 - 9*a*D_n-i-2;
so the new b-value is 9*the old a-value, where a-values are some D_k and b-values are a-1)
Thus I saw D_n = 9*D_n-1 + 1, which is easily shown by induction.
Then I looked at the sum, where the terms 8*D_n + 1 appear, so similar to 9*D_n + 1, and actualy
8*D_n + 1 = 9*D_n + 1 - D_n = D_n+1 - D_n.
And then, with the idea of a geometric series, I finally noticed, that
9 * (D_n+1 - D_n) = 9*D_n+1 + 1 - 9*D_n - 1 = D_n+2 - D_n+1.

• Nole Cuber 10 months ago +7

What software do you use to write your notes on?