HSC 2015 MX2 Marathon (archive) (2 Viewers)

InteGrand · Jul 27, 2015

Re: HSC 2015 4U Marathon

Librah said:
Simplify/sum the following 1+2^2+3^2+4^2+5^2.....n^2.

http://www.math.com/tables/expansion/power.htm

$Method: Expand and simplify $(k+1)^3 - k^3$ and you get a quadratic in $k$. Rearrange to make $k^2$ the subject on the L.H.S. and then sum both sides from $k=1$ to $n$, using a telescoping sum and sum of an AP on the R.H.S. (the L.H.S. is the desired power sum).$

Librah · Jul 28, 2015

Re: HSC 2015 4U Marathon

InteGrand said:
http://www.math.com/tables/expansion/power.htm

$Method: Expand and simplify $(k-1)^3 - k^2$ and you get a quadratic in $k$. Rearrange to make $k^2$ the subject on the L.H.S. and then sum both sides from $k=1$ to $n$, using a telescoping sum and sum of an AP on the R.H.S. (the L.H.S. is the desired power sum).$

do you mean (k-1)^3 - k^3? But yeah, this works.

I was thinking of a way using complex numbers to generalize for k^n then solving. But that would probably just complicating things.

InteGrand · Jul 28, 2015

Re: HSC 2015 4U Marathon

Librah said:
do you mean (k-1)^3 - k^3? But yeah, this works.

I was thinking of a way using complex numbers to generalize for k^n then solving. But that was probably just complicating things.

$Lol yeah, typo, meant $(k+1)^3 - k^3$.$

Drsoccerball · Jul 28, 2015

Re: HSC 2015 4U Marathon

InteGrand said:
$Lol yeah, typo, meant $(k+1)^3 - k^3$.$

can you show

InteGrand · Jul 28, 2015

Re: HSC 2015 4U Marathon

Drsoccerball said:
can you show

I can't be bothered typing it out now, but it's the proof given here: https://proofwiki.org/wiki/Sum_of_Sequence_of_Squares/Proof_5

braintic · Jul 28, 2015

Re: HSC 2015 4U Marathon

Alternatively, recognise that the sum of quadratic terms must have cubic form.
So write S_n = an^3 + bn^2 + cn
(the constant term must be zero so that S_0 = 0)

Then sub in the expected sums for n=1,2,3 and solve simultaneously to find a,b,c.

Sy123 · Jul 28, 2015

Re: HSC 2015 4U Marathon

Librah said:
Simplify/sum the following 1+2^2+3^2+4^2+5^2.....n^2.

Alternative to proof given by InteGrand

$k^2 = 2\binom{k}{2} + \binom{k}{1}$

$\sum_{k=1}^n k^2 = 2\sum_{k=1}^n \binom{k}{2} + \sum_{k=1}^n \binom{k}{1}$

$\\ $Consider the geometric sum$ \\ \\ (1+x) + (1+x)^2 + \dots + (1+x)^n = \frac{1+x}{x} ((1+x)^{n} - 1)$

$\\ $2 times the co-efficient of$ \ x^2 \ $plus the co-efficient of$ \ x \ $on the LHS is equal to$ \ 2\sum_{k=1}^n \binom{k}{2} + \sum_{k=1}^n \binom{k}{1} = \sum_{k=1}^n k^2 \\ \\ $So, this sum on the RHS is$ \ 2\binom{n}{3} + 3 \binom{n}{2} + \binom{n}{1} \\ \\ $Therefore$ \ \sum_{k=1}^n k^2 = 2\binom{n}{3} + 3\binom{n}{2} + \binom{n}{1} = \frac{n}{6}(n+1)(2n+1)$

Sy123 · Jul 28, 2015

Re: HSC 2015 4U Marathon

braintic said:
Alternatively, recognise that the sum of quadratic terms must have cubic form.

I'd add that one way to prove this is by proving the sum is a polynomial (by induction, since if S_n is a polynomial, then S_(n+1) = S_n + (n+1)^2 is a polynomial), and that it's a cubic since the sum is less than:

$\int_1^n x^2 = \frac{n^3}{3} - \frac{1}{3}$

(by the lower rectangles being less than the curve)
which is a cubic, so it's degree is at most a cubic (since if it was higher, then for sufficiently large N the inequality is violated)

Sy123 · Jul 28, 2015

Re: HSC 2015 4U Marathon

$\\ $Consider the polynomial$ \ p(x) = (x+\alpha)^3 - 27\beta x \ $for positive$ \ \alpha, \beta \\\\ $i) Show that if$ \ x \geq 0 \ $and$ \ \alpha^2 \geq 4\beta \ $, then$ \ p(x) \geq 0$

$\\ $ii) Hence, show that$ \ \frac{a+b+c}{3} \geq \sqrt[3]{abc} \ $for positive$ \ a,b,c$

$\\ $iii) (extension) Prove similarly the inequality$ \ \frac{x_1 + x_2 + \dots + x_n}{n} \geq \sqrt[n]{x_1x_2\dots x_n}$

InteGrand · Jul 28, 2015

Re: HSC 2015 4U Marathon

Sy123 said:
I'd add that one way to prove this is by proving the sum is a polynomial (by induction, since if S_n is a polynomial, then S_(n+1) = S_n + (n+1)^2 is a polynomial)

What would we do for the base case for this?

Kaido · Jul 28, 2015

Re: HSC 2015 4U Marathon

wth, proofwiki ahahha

interesting method to approach the amgm proof, was that in previous exams or did u come up with it sy :O

Sy123 · Jul 28, 2015

Re: HSC 2015 4U Marathon

Kaido said:
wth, proofwiki ahahha

interesting method to approach the amgm proof, was that in previous exams or did u come up with it sy :O

I 'came up with it' when I was trying to find a way to get 2U students to prove the AM-GM for n=2, but then I realized it could be generalized quite easily haha (with the aid of induction)

But I'm sure it's been thought of before

Sy123 · Jul 28, 2015

Re: HSC 2015 4U Marathon

InteGrand said:
What would we do for the base case for this?

good point (idk)

glittergal96 · Jul 29, 2015

Re: HSC 2015 4U Marathon

Sy123 said:
I'd add that one way to prove this is by proving the sum is a polynomial (by induction, since if S_n is a polynomial, then S_(n+1) = S_n + (n+1)^2 is a polynomial)

I don't think this works, we need a fixed polynomial that evaluates the n-th partial sum.

Here is a way of proving that it is a degree d+1 polynomial (where d is the power we are raising the terms to).

Suppose by inductive hypothesis that:

$S_l(n)=\sum_{k=1}^n k^l=p_l(n)$

for $0\leq l < d$ , where $\deg(p_l)=l+1.$

Then

$(n+1)^{d+1}-1 = \sum_{k=1}^n ((k+1)^{d+1}-k^{d+1})=\sum_{l=0}^d\binom{d+1}{l}S_l(n)$

by expanding out binomially to obtain the last equality.

So

$S_d(n)=\frac{1}{d+1}\left((n+1)^{d+1}-1-\sum_{l=0}^{d-1}\binom{d+1}{l}p_l(n)\right)$

is a degree d+1 polynomial from our inductive hypothesis.

I suppose this also gives you a way of recursively computing these polynomials but it probably gets tedious fast.

glittergal96 · Jul 29, 2015

Re: HSC 2015 4U Marathon

Another approach that is nice and works is to consider the recurrence relation

$u_n-u_{n-1}=p(n),u(0)=0.$

for polynomials p of degree d. (When p(x) is the monomial x^d, finding a closed solution to the recurrence is the same thing as finding a closed form for S_d(n).)

We can prove inductively that the solution to such recurrences is a polynomial of degree d+1.

Idea: Make the substitution $u_n=v_n+an^{d+1}$ where a is an arbitrary parameter.

Substituting then translates our u-recurrence into a v-recurrence with the parameter a floating around.

BUT by choosing "a" to be a particular value, the top order term of the polynomial on the RHS of the recurrence vanishes, and we have reduced the problem to one of lower degree, which we already know has a polynomial solution of deg < d+1.

So this also tells us that u is a polynomial of degree d+1 in n.

(I prefer this way because the techniques are more general/powerful and the result is stronger.)

glittergal96 · Jul 29, 2015

Re: HSC 2015 4U Marathon

Sy123 said:
$\\ $Consider the polynomial$ \ p(x) = (x+\alpha)^3 - 27\beta x \ $for positive$ \ \alpha, \beta \\\\ $i) Show that if$ \ x \geq 0 \ $and$ \ \alpha^2 \geq 4\beta \ $, then$ \ p(x) \geq 0$

$\\ $ii) Hence, show that$ \ \frac{a+b+c}{3} \geq \sqrt[3]{abc} \ $for positive$ \ a,b,c$

$\\ $iii) (extension) Prove similarly the inequality$ \ \frac{x_1 + x_2 + \dots + x_n}{n} \geq \sqrt[n]{x_1x_2\dots x_n}$

I might as well just prove the inductive step of your extension question, as the same method is how we answer the earlier parts of the question.

Consider the polynomial $p(x)=(x+a)^n-bx$ .

By considering its first two derivatives, it has at most two stationary points, only one of which: $-a+(b/n)^{\frac{1}{n-1}}$ is potentially positive.

As $p(0)=a\geq 0$ and $\lim_{x\rightarrow\infty}p(x)= \infty$ , p can only attain negative values on the non-negative real line if it has a non-negative stationary point $x_s$ and $p(x_s)<0.$

Simple algebraic manipulations now give us an inequality a and b must satisfy in order to give us $p(x_s)\geq 0$ .

$p(x_s)=(b/n)^{\frac{n}{n-1}}-b(-a+(b/n)^{\frac{1}{n-1}})\geq 0$

$\Rightarrow a^{n-1}\geq \frac{b}{n}\left(\frac{n-1}{n}\right)^{n-1}.\quad (*)$

Given the form of p, it is natural to take $x=x_n/n$ and $a=\frac{1}{n}\sum_{i<n} x_i$ and $b=n\prod_{i<n}x_i$ .

The n-variable AM-GM is then precisely the statement that p(x) is non-negative for non-negative x. So then suffices to show that our a and b satisfy the previously established criterion for non-negativity.

We do this using the assumption of the (n-1) case of AM-GM. (Of course for the original n=3 question, we can use the fact that the n=2 version of AM-GM is extremely easy. Or we could start the induction at the completely trivial n=1 as well probably.)

$(b/n)=\prod_{i<n}x_i\leq \left(\frac{1}{n-1}\sum_{i<n}x_i\right)^{n-1}=\left(\frac{n}{n-1}(a-x)\right)^{n-1}\leq \left(\frac{na}{n-1}\right)^{n-1}$

which upon rearrangement gives us (*) and completes the proof.

kawaiipotato · Aug 2, 2015

Re: HSC 2015 4U Marathon

$New question$

$\sum_{k=1}^{\infty}\frac{k}{a^{k-1}}$

porcupinetree · Aug 2, 2015

Re: HSC 2015 4U Marathon

kawaiipotato said:
$New question$

$\sum_{k=1}^{\infty}\frac{1}{a^{k-1}}$

Just seems like an average 2U question unless I'm misreading something

https://imgur.com/u8J8HIV

VBN2470 · Aug 2, 2015

Re: HSC 2015 4U Marathon

porcupinetree said:
Just seems like an average 2U question unless I'm misreading something

https://imgur.com/u8J8HIV

That's assuming $|a| > 1$ , what happens when $|a|\leq{1}$ ?

kawaiipotato · Aug 2, 2015

Re: HSC 2015 4U Marathon

Was suppose to be k/(a^(k-1)) oops

HSC 2015 MX2 Marathon (archive) (2 Viewers)

Well-Known Member

Not_the_pad

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

This too shall pass

This too shall pass

This too shall pass

Well-Known Member

be.

This too shall pass

This too shall pass

Active Member

Active Member

Active Member

Well-Known Member

not actually a porcupine

Well-Known Member

Well-Known Member

Users Who Are Viewing This Thread (Users: 0, Guests: 2)