Mathematics

9:00 PM

@quid I am looking at this exercise: Use induction to show that if $n$ is a power of $2$ then the solution of the recurrence relation

$$\left\{\begin{matrix}
2 &, \text{ if } n=2 \\
2T\left( \frac{n}{2} \right )+n & , \text{ if } n=2^k, \text{ for } k>1
\end{matrix}\right.$$

is $T(n)=n \lg n$.

@quid That's what I have tried:

We will use induction on $k$ to show that $T(2^k)=2^k \cdot k$.

For $k=1 \Rightarrow n=2^1=2$ we have: $T(2)=2=2 \lg 2 \checkmark$.

We suppose that for some $k \geq 1$ it holds that $T(2^k)=2^k \cdot k$.

For $k+1$: $T(2^{k+1})=2T\left( \frac{2^{k+1}}{2} \right )+2^{k+1}=2T(2^k)+2^{k+1} \overset{\text{induction hypothesis}}{=}2 \cdot 2^k \cdot k+2^{k+1}=2^{k+1} \cdot k+2^{k+1}=2^{k+1}(k+1)$.

Thus, $\forall k \in \mathbb{N}$ it holds that $T(2^k)=2^k \cdot k$.

quid

Looks good to me @evinda

evinda

@quid A ok... or do I have to mention in each case also the form that n will have?

Huy

@DanielFischer: Do you think high schoolers could be motivated enough for me to successfully host a seminar?

Daniel Fischer

@Huy Few things are impossible. You mean holding a seminar with the high schoolers giving the talks? Could work, but be sure that they make a motivated impression before you start planning the seminar.

quid

@evinda You could add a phrase at the start that showing it holds for all $n$ a power of two amounts to showing it for all 2^k with k some positive integer. And that lg(2^k) = k. I would not consider it as necessary. But it cannot hurt, and somebody else might consider it as necessary.

Huy

9:09 PM

@DanielFischer: My course on Game Theory starts tomorrow, and I was thinking of asking whether they'd be motivated enough to do it, each pair one talk. I wrote a short text on the topics I wanted to cover and each pair would briefly summarise and demonstrate 1-2 chapters and present their solution to exercises, maybe during an hour. I'm just a bit afraid once a pair has presented their part, they will be bored and don't listen to other speakers anymore (and don't see the point in attending).

TBH the latter is a problem for university seminars, even, imo.

@DanielFischer: Since it's an optional course, everyone who enrolled is obviously interested and wants to do math (there were such courses in PE, music, art, etc. which would be much "less work", if you will), but it shouldn't be too much work either (and I have a hard time remembering how much work was too much work for me in those times).

Daniel Fischer

@Huy Right, the loss of interest also happens at university.

@Huy Sounds like you could give it a try.

Huy

@DanielFischer: The difference IMO is that many people only attend seminars because they are forced to by the study regulations. Maybe I could ask if it was okay to everyone and if someone e.g. completely dislikes the idea of giving a presentation, I could do it but they'd still have to solve the corresponding exercises.

The real trouble, as said, is how to keep them motivated. They're still kids, after all.

I was thinking about letting pairs who already had their presentation play some games, like chess or Hex. :D

(there is always a session for preperation between the presentations)

evinda

@quid So could I say something like that at the beginning?
We want to show that if $n$ is some power of $2$, then the solution of the recurrence relation is $T(n)=n \lg n$. So it suffices to show it for $n=2^k$ with $k$ some positive integer.
Or could I improve something? :/

quid

@evinda it is good! I would say: "this means to show it" rather than "it suffices to show it" since it is more a rewording than a reduction but this is a minor detail.

(I need to leave for a couple of minutes to find food but will be back then.)

Daniel Fischer

@Huy Of course you need to ask whether they would want to do that. Don't force a kid to give a talk that doesn't want to do it.

Huy

9:21 PM

@DanielFischer: I think many language teachers would disagree. And I was also forced to give talks in geography, biology and other subjects, iirc.

evinda

$k=\sum_{i=0}^{m-(j+1)} a_{i+j+1} x^k$

At the step when $j=d$:

$k=\sum_{i=0}^{m-(d+1)} a_{i+d+1} x^i$

Then when $j=d-1$:

$k=a_{d-1}+x \sum_{i=0}^{m-(d+1)} a_{i+d+1}x^i=a_{d-1}+x \sum_{i=0}^{m-(d+1)} a_{i+d+1}x^{i+1}=a_{d-1}+\sum_{n=1}^{m-d} a_{n+d} x^n$

Daniel Fischer

@Huy Oh, I meant in that situation, with a non-compulsory course. You want them to enjoy the optional things, not to avoid them whenever possible.

evinda

@DanielFischer How can we write the whole expression as the sum $\sum_{i=0}^{m-d} a_{i+d} x^i$? We could do that if the index of the term outside the sum would be j and not j-1, right?

Huy

@DanielFischer: I see, yes, I really want them to enjoy it. I was really surprised enough of them signed up for it to take place.

Balarka Sen

@MikeMiller I think I figured it out, but I am not sure. Consider $\Delta_{\alpha \beta} : S^2 \to S^2$ obtained from attaching a cube to the three 2-cells appropriately (identifying opposite faces in the cube to one of the cells) and then quotienting out everything but one of the cells.

Daniel Fischer

9:28 PM

@Huy A good sign.

evinda

We want to show that if $n$ is some power of $2$, then the solution of the recurrence relation is $T(n)=n \lg n$. This means that we want to show that for $n=2^k$ with $k$ some positive integer the solution is $T(2^k)=2^k \cdot k$.
So could I say it like that? @quid

Bill Dubuque

@robjohn Big missed opportunity. Keep polishing that Bezouka!

Balarka Sen

This is simply equivalent to take a sphere instead, the opposite faces being the northern and southern hemispheres and the rest of the faces squashed in the equatorial circle, and pasting the hemispheres into a 2-cell, followed by punching of the boundary of the 2-cell pasted along with the equator.

infinitesimal

@BillDubuque Hi

Balarka Sen

This is easily seen to be a map that is homotopic to the identity. So degree should be clearly $0$.

But I am not sure about this as Hatcher uses local degree to prove this @Mike

quid

9:39 PM

@evinda: this seems like a very nice way to phrase it to me.

Balarka Sen

Hi @Ted

Transcript for

$Mathematics$ Mathematics