HSC 2016 MX2 Marathon ADVANCED (archive) (3 Viewers)

seanieg89 · Jul 24, 2016

Re: HSC 2016 4U Marathon - Advanced Level

Written as intended, in step 2 you are only dealing with finite sums and integration is not the only thing you are doing in step 4. I just didn't want to be too explicit/prescriptive about the limiting argument, as methods will vary depending on level of mathematical knowledge.

If you naively allow exchanges of infinite series and integrals, then this calculation gives you zeta(2) quite speedily. If any university students attempt this, I would hope for a little more care.

seanieg89 · Jul 28, 2016

Re: HSC 2016 4U Marathon - Advanced Level

And a more algebraic question:

$For a function $f:\mathbb{N}\rightarrow \mathbb{N}$, we define it's \emph{forward difference} by $(\Delta f)(n)=f(n+1)-f(n)$. (In many ways, $\Delta$ is a discrete analogue to differentiation, where $(Sf)(n):=\sum_{k\leq n} f(k)$ is a discrete analogue to integration. Keeping this principle in mind will help if you have trouble with this question.)\\ \\ 1. Show that $\Delta$ transforms nonconstant polynomials to polynomials of one degree lower.\\ \\2. What does $\Delta$ do to the polynomials\\$P_k(n):=\binom{n}{k}?$\\ \\3. Prove that for non-negative integers $d$, the sum \\$\sum_{k\leq n}k^d$\\ is a polynomial of degree $d+1$ in $n$.\\ \\ 4. Find an closed form for this sum. Your expression can contain summations, but any summation in your expression cannot have an index set dependent on $n$. Eg, the trivial expression\\ $\sum_{k\leq n}k^d$ \\itself is not considered a closed form!$

Sy123 · Oct 6, 2016

Re: HSC 2016 4U Marathon - Advanced Level

seanieg89 said:
And a more algebraic question:

$For a function $f:\mathbb{N}\rightarrow \mathbb{N}$, we define it's \emph{forward difference} by $(\Delta f)(n)=f(n+1)-f(n)$. (In many ways, $\Delta$ is a discrete analogue to differentiation, where $(Sf)(n):=\sum_{k\leq n} f(k)$ is a discrete analogue to integration. Keeping this principle in mind will help if you have trouble with this question.)\\ \\ 1. Show that $\Delta$ transforms nonconstant polynomials to polynomials of one degree lower.\\ \\2. What does $\Delta$ do to the polynomials\\$P_k(n):=\binom{n}{k}?$\\ \\3. Prove that for non-negative integers $d$, the sum \\$\sum_{k\leq n}k^d$\\ is a polynomial of degree $d+1$ in $n$.\\ \\ 4. Find an closed form for this sum. Your expression can contain summations, but any summation in your expression cannot have an index set dependent on $n$. Eg, the trivial expression\\ $\sum_{k\leq n}k^d$ \\itself is not considered a closed form!$

$\\ $1. Considering a polynomial of degree$ \ d \ $then$ \ f(n) = \sum_{i=0}^d a_i n^i, (\Delta f)(n) = \sum_{i=0}^d a_i ((n+1)^i - n^i) = \sum_{i=0}^d a_i(\sum_{j=0}^{i-1} \binom{i}{j} n^j) \\\\ $The inner sum is a polynomial of degree$ \ i-1 \ $and so$ \ (\Delta f)(n) \ $is a sum of polynomials of degree at most$ \ d-1 \ $and the coefficient of the term of power$ \ d-1 \ $is$ \ a_d \binom{d}{d-1} \ $which isn't zero since by assumption$ \ f \ $is a degree$ \ d $polynomial so its leading coefficient is non-zero$$

$\\ $2. We get$ \ P_{k-1}(n) \ $by the familiar identity$ \ \binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k}$

$\\ $3. We proceed by induction on$ \ d \ $the statement is true for$ \ d=0 \ $as$ \ \sum_{k\leq n} k^0 = n \ $which is a polynomial in degree$ \ 1 \\\\ $Take the assumption that the statement is true for some$ \ m \ $where$ \ \sum_{k \leq n} k^m \ $is a polynomial of degree$ \ m+1 \ $and that this statement is true for all non-negative integers$ \ 0 \leq i \leq m \\\\ $Now, we seek to prove that$ \ \sum_{k \leq n} k^{m+1} \ $is a polynomial in degree$ \ m+2$
$\\ $First, consider that$ \ k^{m+1} + \sum_{i=0}^m \binom{m+2}{i} k^i = (k+1)^{m+2} - k^{m+2} \\\\ $Now summing both sides from$ \ k=1,\dots, n \ $we get$ \\\\ \sum_{k\leq n} k^{m+1} + \sum_{i=0}^m \binom{m+2}{i} \sum_{k \leq n} k^i = (n+1)^{m+2} - 1 \\\\ $So, $ \ \sum_{k \leq n} k^{m+1} = (n+1)^{m+2} - \sum_{i=0}^m \binom{m+2}{i} P_{i}(n) - 1 \\\\ $Finally, since by assumption$ \ P_i \ $is a polynomial in$ \ i+1 \ $then its sum is a polynomial of at most degree$ \ m+1 \ $implying that$ \ \sum_{k \leq n} k^{m+1} \ $is a polynomial in degree$ \ m+2$

$\\ $4. Let$ \ f_d(n) = \sum_{k\leq n} k^d \\\\ $Now, $ \ (\Delta f_d)(n) = (n+1)^d = \sum_{i=0}^d \binom{d}{i} n^i \\\\ \sum_{k=1}^n (k+1)^d = \sum_{k=1}^n \sum_{i=0}^d \binom{d}{i} k^i = f_d(n) + \sum_{i=0}^{d-1} \binom{d}{i} f_i(n) \\\\ (n+1)^d - 1 + f_d(n) = f_d(n) + \sum_{i=0}^{d-1} \binom{d}{i} f_i(n) \\\\ (n+1)^{d+1} - 1 = \sum_{i=0}^d \binom{d+1}{i} f_i(n) \\\\ \Rightarrow f_d(n) = \frac{1}{d} \left((n+1)^{d+1} - 1 - \sum_{i=0}^{d-1} \binom{d+1}{i} f_i(n) \right) \\\\ $This is a closed expression because we can compute inductively and finitely$ \ f_d(n) \ $for arbitrary$ \ d$

Paradoxica · Oct 6, 2016

Re: HSC 2016 4U Marathon - Advanced Level

Sy123 said:
$\\ $1. Considering a polynomial of degree$ \ d \ $then$ \ f(n) = \sum_{i=0}^d a_i n^i, (\Delta f)(n) = \sum_{i=0}^d a_i ((n+1)^i - n^i) = \sum_{i=0}^d a_i(\sum_{j=0}^{i-1} \binom{i}{j} n^j) \\\\ $The inner sum is a polynomial of degree$ \ i-1 \ $and so$ \ (\Delta f)(n) \ $is a sum of polynomials of degree at most$ \ d-1 \ $and the coefficient of the term of power$ \ d-1 \ $is$ \ a_d \binom{d}{d-1} \ $which isn't zero since by assumption$ \ f \ $is a degree$ \ d $polynomial so its leading coefficient is non-zero$$

$\\ $2. We get$ \ P_{k-1}(n) \ $by the familiar identity$ \ \binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k}$

$\\ $3. We proceed by induction on$ \ d \ $the statement is true for$ \ d=0 \ $as$ \ \sum_{k\leq n} k^0 = n \ $which is a polynomial in degree$ \ 1 \\\\ $Take the assumption that the statement is true for some$ \ m \ $where$ \ \sum_{k \leq n} k^m \ $is a polynomial of degree$ \ m+1 \ $and that this statement is true for all non-negative integers$ \ 0 \leq i \leq m \\\\ $Now, we seek to prove that$ \ \sum_{k \leq n} k^{m+1} \ $is a polynomial in degree$ \ m+2$
$\\ $First, consider that$ \ k^{m+1} + \sum_{i=0}^m \binom{m+2}{i} k^i = (k+1)^{m+2} - k^{m+2} \\\\ $Now summing both sides from$ \ k=1,\dots, n \ $we get$ \\\\ \sum_{k\leq n} k^{m+1} + \sum_{i=0}^m \binom{m+2}{i} \sum_{k \leq n} k^i = (n+1)^{m+2} - 1 \\\\ $So, $ \ \sum_{k \leq n} k^{m+1} = (n+1)^{m+2} - \sum_{i=0}^m \binom{m+2}{i} P_{i}(n) - 1 \\\\ $Finally, since by assumption$ \ P_i \ $is a polynomial in$ \ i+1 \ $then its sum is a polynomial of at most degree$ \ m+1 \ $implying that$ \ \sum_{k \leq n} k^{m+1} \ $is a polynomial in degree$ \ m+2$

$\\ $4. Let$ \ f_d(n) = \sum_{k\leq n} k^d \\\\ $Now, $ \ (\Delta f_d)(n) = (n+1)^d = \sum_{i=0}^d \binom{d}{i} n^i \\\\ \sum_{k=1}^n (k+1)^d = \sum_{k=1}^n \sum_{i=0}^d \binom{d}{i} k^i = f_d(n) + \sum_{i=0}^{d-1} \binom{d}{i} f_i(n) \\\\ (n+1)^d - 1 + f_d(n) = f_d(n) + \sum_{i=0}^{d-1} \binom{d}{i} f_i(n) \\\\ (n+1)^{d+1} - 1 = \sum_{i=0}^d \binom{d+1}{i} f_i(n) \\\\ \Rightarrow f_d(n) = \frac{1}{d} \left((n+1)^{d+1} - 1 - \sum_{i=0}^{d-1} \binom{d+1}{i} f_i(n) \right) \\\\ $This is a closed expression because we can compute inductively and finitely$ \ f_d(n) \ $for arbitrary$ \ d$

how long did that take you....

Sy123 · Oct 6, 2016

Re: HSC 2016 4U Marathon - Advanced Level

$\\ $Consider the set of well-formed arithmetic sentences$ \ A \ $defined inductively as follows$ \\\\ $1. Any variable symbol denoting a variable is in$ \ A \\ $2. If$ \ \alpha \ $and$ \ \beta \ $are both sentences in$ \ A \ $then$ \ (\alpha + \beta), (\alpha - \beta), (\alpha \times \beta), (\alpha \div \beta) \ $are all in$ \ A \\ $3. No other sentence is in$ \ A \\\\ $Let$ \ a \ $be a sentence in$ \ A \ $and$ \ v(a) \ $be the number of variables in$ \ a \ $and$ \ b \ $be the number of times$ \ +, -, \times, \div \ $appear in$ a \\\\ $Show that for all$ \ a \ $in$ \ A \ $then$ \ p(a) = b(a) + 1$

Sy123 · Oct 6, 2016

Re: HSC 2016 4U Marathon - Advanced Level

Sy123 said:
$\\ $Consider the set of well-formed arithmetic sentences$ \ A \ $defined inductively as follows$ \\\\ $1. Any variable symbol denoting a variable is in$ \ A \\ $2. If$ \ \alpha \ $and$ \ \beta \ $are both sentences in$ \ A \ $then$ \ (\alpha + \beta), (\alpha - \beta), (\alpha \times \beta), (\alpha \div \beta) \ $are all in$ \ A \\ $3. No other sentence is in$ \ A \\\\ $Let$ \ a \ $be a sentence in$ \ A \ $and$ \ v(a) \ $be the number of variables in$ \ a \ $and$ \ b \ $be the number of times$ \ +, -, \times, \div \ $appear in$ a \\\\ $Show that for all$ \ a \ $in$ \ A \ $then$ \ p(a) = b(a) + 1$

$\\ $Extend our set$ \ A \ $as follows with the additional rule:$ \\\\ $- If$ \ \alpha \ $is a sentence in$ \ A \ $then$ \ (f\alpha) \ $(denoting some function$ \ f $) is in$ \ A$

$\\ $If$ \ a \ $is a sentence in$ \ A \ $let$ \ l(a) \ $be the number of brackets in the expression, and let$ \ t(a) \ $be the number of times the function$ \ f \ $appears in the expression, for example in the expression, $\ a: ((x + y) - (fx)) \\ $then$ \ l(a) = 6,\ b(a) = 2, \ t(a) = 1$

$\\ $Show that$ \ 2(b(a) + t(a)) = l(a) \ $for any expression$ \ a \ $in$ \ A$

seanieg89 · Oct 7, 2016

Re: HSC 2016 4U Marathon - Advanced Level

Sy123 said:
$\\ $1. Considering a polynomial of degree$ \ d \ $then$ \ f(n) = \sum_{i=0}^d a_i n^i, (\Delta f)(n) = \sum_{i=0}^d a_i ((n+1)^i - n^i) = \sum_{i=0}^d a_i(\sum_{j=0}^{i-1} \binom{i}{j} n^j) \\\\ $The inner sum is a polynomial of degree$ \ i-1 \ $and so$ \ (\Delta f)(n) \ $is a sum of polynomials of degree at most$ \ d-1 \ $and the coefficient of the term of power$ \ d-1 \ $is$ \ a_d \binom{d}{d-1} \ $which isn't zero since by assumption$ \ f \ $is a degree$ \ d $polynomial so its leading coefficient is non-zero$$

$\\ $2. We get$ \ P_{k-1}(n) \ $by the familiar identity$ \ \binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k}$

$\\ $3. We proceed by induction on$ \ d \ $the statement is true for$ \ d=0 \ $as$ \ \sum_{k\leq n} k^0 = n \ $which is a polynomial in degree$ \ 1 \\\\ $Take the assumption that the statement is true for some$ \ m \ $where$ \ \sum_{k \leq n} k^m \ $is a polynomial of degree$ \ m+1 \ $and that this statement is true for all non-negative integers$ \ 0 \leq i \leq m \\\\ $Now, we seek to prove that$ \ \sum_{k \leq n} k^{m+1} \ $is a polynomial in degree$ \ m+2$
$\\ $First, consider that$ \ k^{m+1} + \sum_{i=0}^m \binom{m+2}{i} k^i = (k+1)^{m+2} - k^{m+2} \\\\ $Now summing both sides from$ \ k=1,\dots, n \ $we get$ \\\\ \sum_{k\leq n} k^{m+1} + \sum_{i=0}^m \binom{m+2}{i} \sum_{k \leq n} k^i = (n+1)^{m+2} - 1 \\\\ $So, $ \ \sum_{k \leq n} k^{m+1} = (n+1)^{m+2} - \sum_{i=0}^m \binom{m+2}{i} P_{i}(n) - 1 \\\\ $Finally, since by assumption$ \ P_i \ $is a polynomial in$ \ i+1 \ $then its sum is a polynomial of at most degree$ \ m+1 \ $implying that$ \ \sum_{k \leq n} k^{m+1} \ $is a polynomial in degree$ \ m+2$

$\\ $4. Let$ \ f_d(n) = \sum_{k\leq n} k^d \\\\ $Now, $ \ (\Delta f_d)(n) = (n+1)^d = \sum_{i=0}^d \binom{d}{i} n^i \\\\ \sum_{k=1}^n (k+1)^d = \sum_{k=1}^n \sum_{i=0}^d \binom{d}{i} k^i = f_d(n) + \sum_{i=0}^{d-1} \binom{d}{i} f_i(n) \\\\ (n+1)^d - 1 + f_d(n) = f_d(n) + \sum_{i=0}^{d-1} \binom{d}{i} f_i(n) \\\\ (n+1)^{d+1} - 1 = \sum_{i=0}^d \binom{d+1}{i} f_i(n) \\\\ \Rightarrow f_d(n) = \frac{1}{d} \left((n+1)^{d+1} - 1 - \sum_{i=0}^{d-1} \binom{d+1}{i} f_i(n) \right) \\\\ $This is a closed expression because we can compute inductively and finitely$ \ f_d(n) \ $for arbitrary$ \ d$

Good stuff

. (Although the denominator should be d+1 in your final answer to 4. Similarly, you have lost a constant factor on your way to the final expression in 3, although of course this does not affect the proof.)

Ps, the expression you obtained at the end of 3 is basically what you were looking for in 4, so you really didn't need to do that calculation again in 4. My intention for 3 was simply to note that any d-th degree polynomial in n (eg n^d) can be written as a linear combination of the polynomials P_k(n) for k =< d, which from the previous part can individually be written as a difference that telescopes.

Sy123 · Oct 29, 2016

Re: HSC 2016 4U Marathon - Advanced Level

Should be simple, but it does not fit in the regular marathon:

$\\ $Let$ \ a,b,c \ $be integers such that$ \ a\sqrt{2} + b\sqrt{3} + c = 0$, prove that$ \ a = b = c = 0$

Paradoxica · Oct 29, 2016

Re: HSC 2016 4U Marathon - Advanced Level

Sy123 said:
Should be simple, but it does not fit in the regular marathon:

$\\ $Let$ \ a,b,c \ $be integers such that$ \ a\sqrt{2} + b\sqrt{3} + c = 0$, prove that$ \ a = b = c = 0$

For anyone attempting this, it is sufficient to do the problem for

$$\noindent$ a\sqrt{2}+b\sqrt{3} = 0$

as the pure integer part is incommensurable with the irrational parts. (recall the definition of an irrational number)

Sy123 · Oct 29, 2016

Re: HSC 2016 4U Marathon - Advanced Level

Paradoxica said:
For anyone attempting this, it is sufficient to do the problem for

$$\noindent$ a\sqrt{2}+b\sqrt{3} = 0$

as the pure integer part is incommensurable with the irrational parts. (recall the definition of an irrational number)

This defeats the purpose of the question, if someone wants to do it this way, they'll need to prove the facts that they'd need to, to use it, along the way.

Paradoxica · Oct 29, 2016

Re: HSC 2016 4U Marathon - Advanced Level

Sy123 said:
This defeats the purpose of the question, if someone wants to do it this way, they'll need to prove the facts that they'd need to, to use it, along the way.

what facts? the separability of the equation is obvious.

also, questions have a purpose now?

you didn't restrict the means of resolving this question.

and doing so defeats the purpose of this whole thread.

Paradoxica · Oct 30, 2016

Re: HSC 2016 4U Marathon - Advanced Level

Sy123 said:
This defeats the purpose of the question, if someone wants to do it this way, they'll need to prove the facts that they'd need to, to use it, along the way.

In any case, the question is still easy, with or without seperation of equations.

The equation rearranges by inspection into:

$\frac{c^2 - 2a^2 - 3b^2}{2ab} = \sqrt{6}$

provided none of a or b is zero (see, told you seperation is obvious)

This would, as a consequence make √6 rational, which is false. Therefore, there does not exist a solution in the case of non-zero a,b

Then a and b are 0 forcing c to be 0.

Now go eat a snickers or something.

seanieg89 · Oct 30, 2016

Re: HSC 2016 4U Marathon - Advanced Level

He isn't "restricting the means" of resolving the question, he is just saying that a solution that jumps in halfway through after an unjustified reduction of the problem is not a complete solution. (And I agree with him.)

I don't think the leap from the question to your reduction is one that high school students should make without careful justification, as I think many of them would either be unable to see why this leap is true or worse, hoodwink themselves into believing that they understand the reduction when they don't.

HSC 2016 MX2 Marathon ADVANCED (archive) (3 Viewers)

seanieg89

Well-Known Member

seanieg89

Well-Known Member

Sy123

This too shall pass

Paradoxica

-insert title here-

Sy123

This too shall pass

Sy123

This too shall pass

seanieg89

Well-Known Member

Sy123

This too shall pass

Paradoxica

-insert title here-

Sy123

This too shall pass

Paradoxica

-insert title here-

Paradoxica

-insert title here-

seanieg89

Well-Known Member

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