HSC 2015 MX1 Marathon (archive) (5 Viewers)

Drsoccerball · Feb 26, 2015

Re: HSC 2015 3U Marathon

Drsoccerball said:
Its becomes:
$1+ k+1 + \frac{(k+2)(k+1)}{2!} +... \frac{(k+n)(k+n-1)}{n!}$

Where 1 is not apart of the series

Sy123 · Feb 26, 2015

Re: HSC 2015 3U Marathon

Drsoccerball said:
Where 1 is not apart of the series

Well give it a go if you think it will work. Also for that expression, I don't know how you simplified:

$\binom{n-1}{k} = \frac{(k+n)(k-1+n)}{n!}$ because that is not true

integral95 · Feb 26, 2015

Re: HSC 2015 3U Marathon

I get the feeling @Drsoccorball is not familiar with binomial theorem yet.

Drsoccerball · Feb 26, 2015

Re: HSC 2015 3U Marathon

integral95 said:
I get the feeling @Drsoccorball is not familiar with binomial theorem yet.

I do extension 2 ahahahahhahahaha

Drsoccerball · Feb 26, 2015

Re: HSC 2015 3U Marathon

Sy123 said:
Well give it a go if you think it will work. Also for that expression, I don't know how you simplified:

$\binom{n-1}{k} = \frac{(k+n)(k-1+n)}{n!}$ because that is not true

The RHS is the last term of the series its not equal to (n-1)Ck

braintic · Feb 26, 2015

Re: HSC 2015 3U Marathon

Sy123 said:
$\\ $Show that$ \ \binom{k}{k} + \binom{k+1}{k} + \dots + \binom{n-1}{k} = \binom{n}{k+1} \ $for$ \ 0 \leq k \leq (n-1) \ $for integers$ \ k,n$

Solution:
View attachment Binom.pdf

Edit: I'm struggling to come up with an alternate combinatorics-based solution for this question. Can anyone come up with one?

Carrotsticks · Feb 27, 2015

Re: HSC 2015 3U Marathon

braintic said:
Solution:
View attachment 31858

Edit: I'm struggling to come up with an alternate combinatorics-based solution for this question. Can anyone come up with one?

$\\ $Consider a group of $ n $ people named $ P_1,P_2,P_3,...,P_n $ from which we wish to select $ k+1 $ people to join a team.$ \\\\ $The number of ways such that $ P_1 $ is guaranteed a spot in the team is $ \binom{n-1}{k}. \\\\ $The number of ways such that $ P_2 $ is guaranteed a spot, whereas $ P_1 $ is excluded from the team is $ \binom{n-2}{k}. \\\\ $Similarly if $ P_3 $ is guaranteed a spot whereas $ P_1 $ and $ P_2 $ are excluded, we have $ \binom{n-3}{k} $ ways of choosing the remainder of the team.$ \\\\ $Continuing this, we acquire the left side of the equation. $ \\\\ $But observe that by cycling through the group like this, we are also cycling through the different combinations of selecting our team of $ k+1 $ members. In other words, this is just another method of counting the ways of choosing $ k+1 $ people from a group of $ n $ people, which is of course given by $ \binom{n}{k+1}.$

FrankXie · Feb 27, 2015

Re: HSC 2015 3U Marathon

well, another way is applying $\binom{m}{l}=\binom{m-1}{l-1}+\binom{m-1}{l}$ (which is a well-known result in any textbook) again and again
$RHS=\binom{n-1}{k}+\binom{n-1}{k+1}=\binom{n-1}{k}+\binom{n-2}{k}+\binom{n-2}{k+1}=\binom{n-1}{k}+\binom{n-2}{k}+\binom{n-3}{k}+\binom{n-3}{k+1}=\cdots=\binom{n-1}{k}+\binom{n-2}{k}+\binom{n-3}{k}+\cdots+\binom{k+1}{k}+\binom{k+1}{k+1}=LHS $ because the last term is $ 1$

SilentWaters · Feb 27, 2015

Re: HSC 2015 3U Marathon

This could work by induction on n. For the base case n = 1, we are forced to have k = 0:

$\sum_{m=k}^0 \binom{m}{0} =\binom{1}{1}$

which is true since both sides equate to 1.

Assuming this is true for $0\leq n\leq s-1$ , where $0\leq k<n$ we make the hypothesis:

$\sum_{m=k}^{s-2}\binom{m}{k} = \binom{s-1}{k+1}$

We finish the inductive step in two cases.

(1) For $0\leq k<s-1$

$\sum_{m=k}^{s-1}\binom{m}{k} = \sum_{m=k}^{s-2}\binom{m}{k} + \binom{s-1}{k}$

which by our assumption is

$\binom{s-1}{k+1} + \binom{s-1}{k} = \binom{s}{k+1}.$

This will hold from Pascal's rule.

(2) k = s - 1

$\sum_{m=s-1}^{s-1}\binom{m}{s-1} = \binom{s}{s-1+1}$

Both sides here equate to 1, and we're done.

EDIT: Missed a case, thank you InteGrand + FrankXie.

FrankXie · Feb 27, 2015

Re: HSC 2015 3U Marathon

SilentWaters said:
This could work by induction on n-1. For the base case (zero):

$\sum_{m=k}^0 \binom{m}{k} = \begin{cases} 1 &\mbox{if } k=0 \\ 0 &\mbox{if } k>0 \end{cases}$

The right hand side produces the same results case-wise.

So assuming this is true up to some n-2, we complete the inductive step using Pascal's rule, as FrankXie mentioned:

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

which equates to

$\binom{n-1}{k+1}+\binom{n-1}{k} = \binom{n}{k+1}.$

there is a flaw when proving by induction, can you find it?

this is a very good example that shows how to fully understand the logic behind induction.

InteGrand · Feb 27, 2015

Re: HSC 2015 3U Marathon

FrankXie said:
there is a flaw when proving by induction, can you find it? this is a very good example that shows how to fully understand the logic behind induction.

Is the flaw that, when we make the assumption for the inductive hypothesis, k can take on certain values only, but in the inductive step, k can also take on one more value, but this value isn't accounted for in the inductive hypothesis?

FrankXie · Feb 27, 2015

Re: HSC 2015 3U Marathon

new question

$$ Find $ \int2^{\ln x}dx.$

VBN2470 · Feb 27, 2015

Re: HSC 2015 3U Marathon

FrankXie said:
new question

$$ Find $ \int2^{\ln x}dx.$

$Note the integrand can be expressed $2^{\ln x}=e^{\ln x \ln2}=x^{\ln2}$ so our integral will be $\frac{x^{1+\ln2}}{1+\ln2}+C$$

FrankXie · Feb 27, 2015

Re: HSC 2015 3U Marathon

next one

$$ Find the exact value of $ \sum_{n=1}^{10}\sin^{-1}(\sin n).$

Sy123 · Feb 27, 2015

Re: HSC 2015 3U Marathon

$\\ $Using the identity$ \ (1+x)^n \left(1+ \frac{1}{x} \right)^n = \frac{1}{x^n}(1+x)^{2n} \ $or otherwise, show that$ \\ \\ \sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}$

SilentWaters · Feb 27, 2015

Re: HSC 2015 3U Marathon

Consider selecting n members for an exec. team from a pool of 2n candidates, where men and women are equally numbered.

On the left-hand side, we use the symmetric property of combinations to change the summation to:

$\sum_{k=0}^n\binom{n}{k}\binom{n}{n-k}$

Now choose 0 men, n women; 1 man, n-1 women; 2 men, n-2 women; and so on and so forth until we have exec teams with all the possible number of men and women.

This gives us the left hand side.

Simply selecting n people from the pool of 2n in the first place gives us the right hand side, and we are done.

Drsoccerball · Feb 27, 2015

Re: HSC 2015 3U Marathon

Sy123 said:
$\\ $Using the identity$ \ (1+x)^n \left(1+ \frac{1}{x} \right)^n = \frac{1}{x^n}(1+x)^{2n} \ $or otherwise, show that$ \\ \\ \sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}$

$$ Equate constant terms of the equation $:$

$RHS= \binom{2n}{n}$

$LHS = \binom{n}{0}^2 +\binom{n}{1}^2 +....+\binom{n}{k}^2$

$\therefore \sum_{k=0}^n\binom{n}{k}^2 =\binom{2n}{k}$

SilentWaters · Feb 27, 2015

Re: HSC 2015 3U Marathon

Frank's one is a bit tedious (unless, of course, there is a shorter way). Accounting for the saw-tooth shape of y = arcsin(sinx), such that each term of the sum oscillates in

$y\in\left[-\frac{\pi}{2}, \frac{\pi}{2} \right]$

we posit the following:

$y = \begin{cases} x-2k\pi &\mbox{if } x\in \left[ 2k\pi, 2k\pi +\frac{\pi}{2} \right] \\ (2k\pi +\pi) -x &\mbox{if }x\in \left[2k\pi +\frac{\pi}{2}, 2k\pi +\pi \right] \\ (2k\pi -\pi )-x &\mbox{if } x\in \left[2k\pi -\pi,2k\pi - \frac{\pi}{2} \right] \\ x-2k\pi &\mbox{if } x\in \left[2k\pi -\frac{\pi}{2}, 2k\pi \right] \end{cases}$

for some integral k. Working from decimal-point approximations of the positive half-pi intervals, we determine which quadrant each value of x falls into. From there, we compute:

$\mbox {\sum_{1}^{10} \sin ^{-1}(\sin x) = 1 + (\pi - 2) + (\pi -3) +(\pi -4) + (5 -2\pi) + (6 -2\pi) + (7 -2\pi) + (3\pi -8) + (3\pi -9) + (3\pi -10) = 6\pi -17}$

FrankXie · Feb 27, 2015

Re: HSC 2015 3U Marathon

SilentWaters said:
Frank's one is a bit tedious (unless, of course, there is a shorter way). Accounting for the saw-tooth shape of y = arcsin(sinx), such that each term of the sum oscillates in

$y\in\left[-\frac{\pi}{2}, \frac{\pi}{2} \right]$

we posit the following:

$y = \begin{cases} x-2k\pi &\mbox{if } x\in \left[ 2k\pi, 2k\pi +\frac{\pi}{2} \right] \\ (2k\pi +\pi) -x &\mbox{if }x\in \left[2k\pi +\frac{\pi}{2}, 2k\pi +\pi \right] \\ (2k\pi -\pi )-x &\mbox{if } x\in \left[2k\pi -\pi,2k\pi - \frac{\pi}{2} \right] \\ x-2k\pi &\mbox{if } x\in \left[2k\pi -\frac{\pi}{2}, 2k\pi \right] \end{cases}$

for some integral k. Working from decimal-point approximations of the positive half-pi intervals, we determine which quadrant each value of x falls into. From there, we compute:

$\mbox {\sum_{1}^{10} \sin ^{-1}(\sin x) = 1 + (\pi - 2) + (\pi -3) +(\pi -4) + (5 -2\pi) + (6 -2\pi) + (7 -2\pi) + (3\pi -8) + (3\pi -9) + (3\pi -10) = 6\pi -17}$

lol as far as i know there is no shorter way, like there is no general formula for $\sum_{k=1}^n\sin^{-1}(\sin k).$

Drsoccerball · Feb 28, 2015

Re: HSC 2015 3U Marathon

In how many ways can 10 identical coins be allocated to 4 different boxes if no box will be left empty

HSC 2015 MX1 Marathon (archive) (5 Viewers)

Well-Known Member

This too shall pass

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Retired

Active Member

Member

Active Member

Well-Known Member

Active Member

Well-Known Member

Active Member

This too shall pass

Member

Well-Known Member

Member

Active Member

Well-Known Member

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