Maths on Steroids: Tute 6

I have no idea why I thought that today was Yom Kippur - especially because I actually thought that it was Jewish New Year's Day: Rosh Hashanah. I suspect that a combination of illness, watching old Family Guy and South Park episodes and stealing a glance (over someone's shoulder on the train) on a Rabbi's chaplaincy report (*) must have caused my mind to mash all of these ingredients into some crazy-festive-kosher-holiday-cake-mix. And if that doesn't make sense, well good - it doesn't make any sense to me either. But let's all hope that the maths that I'm about to write does make sense.

Sooooo guys, remember this question from your assignment?

"Find an \(n_0\) such that for all \(n\geq n_0\), \(3^n>n^4\). Give a proof by induction."

Well, it's pretty painful for me to mark a proof by induction by induction in an induction in an induction (**), so I'm going to remind you guys that comparison trick that I showed you in the tutes...obviously, I'm only going to do the induction step, and I'll forgo the usual setting-up:

Assume that \(3^k>k^4\) is true, let's show that \(3^{k+1}>(k+1)^4.\)

Well, since \(k\geq 8\) - this follows from the base case holding for \(n_0=8\), we obtain the following sequence of inequalities:\begin{align}3^{k+1}> k^4+2k^4&\geq k^4+16k^3\\&=k^4+4k^3+12k^3\\&\geq k^4+4k^3+96k^2\\&>k^4+4k^3+6k^2+4k+1=(k+1)^4.\end{align} Note that I've tweaked it a tiny bit from what we did in class - just because \(k\geq 8\), doesn't mean that your inequalities always have to be of the form \(k^{m+1}\geq 8 k^{m}\). Speaking of tweaking stuff, Nick came up with a cute version of this comparison trick in his assignment. If you don't mind fractions, you can just straight off use that:\begin{align}k^4+4k^3+6k^2+4k+1\leq(1+\frac{4}{8}+\frac{6}{8^2}+\frac{4}{8^3}+\frac{1}{8^4})k^4=\frac{6561}{4096}k^4<3k^4<3^{k+1}.\end{align}

Oh, and one final comment before we go through the MATLAB graphing code from this week's tutorial: be aware of the flow of your logical arguments. I understand that sometimes your thinking as you progress through a proof is pragmatic, it's like: to get A, I need B; to get B, I need C...etc. But when it's written simply in the form: A, B, C, ... with no (backwards) implication arrows, I'm going to assume that you mean that A implies B and B implies C and so forth.

Orrite, MATLAB time! First things first, here's the code for the m-file that I used to generate the MATLAB plot during Tuesday's lab:

x=-3:0.1:3;
n=length(x);
y=[];
for k=1:n
    if x(k)<-2
        y(k)=0;
    elseif x(k)<0
        y(k)=x(k)^2;
    else
        y(k)=x(k)^3+2;
    end
end
plot(x,y,'*')

Ultimately, we want to produce a graph (of points) by the end of this exercise using MATLAB's "plot" function. Now, plot works by taking in two vectors of the same length \(x\) and \(y\) and using them respectively as the \(x\) and \(y\)-coordinates of the points that we wanna plot. And specifying '*' or 'x' or '+' or '-' in the third entry in plot(x,y,'*') tells MATLAB what type of points it should draw. If you just type plot(x,y), MATLAB will "join the dots" by default - try it out and see what happens!

Let's break it down, line by line:

1. We create a vector \(x=[-3, -2.9, -2.8,\ldots, 2.9, 3]\). This will constitute the \(x\)-values of the points that we'll draw.
2. Since we need to create a vector of \(y\)-values of the same length, I decided to create a variable \(n\) that keeps track of the length of \(x\).
3. We create a vector called \(y\) that at the moment is empty. As in, it's a length zero vector. This step is, I think, unnecessary in MATLAB, but I dunno, I see it around every so often - maybe it's important in another programming language? If anyone knows, tell me. =P
4. We start out for-loop. Note that \(1:n\) creates a vector of the form\[[1,2,3,\ldots,n-2,n-1,n],\]and for loop basically goes through this vector and runs everything inside of the for-loop (i.e.: lines 5~11) first for \(k=1\), then for \(k=2\), then for \(k=3\),...etc., until \(k=n\). 
5. This is the beginning of our if-loop inside of our for-loop. And the first condition is to check if the \(k\)th value of the vector \(x\) is less than -2. So recall: \(x(k)\) means the \(k\)th value of \(x\).
6. If the condition of \(x(k)<-2\) is satisfied, then we set the \(k\)th value of the vector \(y\) to be \(0\). Note that if \(y\) is shorter than length \(k\), this step implicitly extends the \(y\) vector to being length \(k\). Just to reiterate: the final outcome of this first portion of the if-loop is that if our \(x\) values are strictly less than \(-2\), our \(y\) is just \(0\). Which is precisely the first part of the hybrid function that we're meant to draw.
7. This second condition of our if-loop checks if the \(k\)th entry of \(x\) is less than \(0\). Note that since the first condition of the if-loop has already taken care of \(x(k)<-2\), this condition is really checking for when \(-2\leq x(k)<0\).
8. Given that the condition that \(-2\leq x(k)<0\) is fulfilled, we assign the \(k\)th entry of the \(y\) vector to be our \(x\) value squared. So, this is just saying that on the domain of \([-2,0)\), we're drawing the graph of \(f(x)=x^2\).
9. This last condition of our if-loop takes in everything-else in our domain (which in this case is \([-3,3]\) - I just picked this domain out of thin air, in the actual MATLAB exam, it should be given). So in this case, we'll end up dealing with \(0\leq x(k)\leq 3\).
10. Much like line 8, this is just saying that on the \([0,3]\) portion of our domain, the graph that we're drawing looks like \(f(x)=x^3+2\).
11. Ends our if-loop.
12. Ends our for-loop. Notice that you can always tell the start and ends of an if or a for loop using the natural indentations that MATLAB introduces.
13. Uses the plot-function native to MATLAB to draw our points on a plane.

Psst: at each step here we put a semi-colon ; at the end of every line where MATLAB does a computation. This stops the program from outputting something on the screen - otherwise you'd get clunky computations appearing in the program console. Try to remove one of those semi-colons and running the program if you wanna see what I mean. Also, the most common mistake that students make with the sort of problem in the MATLAB exam is to write \(x\) instead of \(x(k)\) and \(y\) instead of \(y(k)\) inside the loops. Always remember that \(x\) and \(y\) are vectors! Another common mistake is to get the conditions for the if-loop wrong, I mean: sometimes you need strict inequalities, sometimes you need non-strict ones.

So, I hope that all made sense, because I'm about to show you some other ways of drawing this graph. Now, recall from the first week that we can concatenate two row-vectors \(w1\) and \(w2\) by writing \([w1,w2]\) in MATLAB. Well, we could have used this to "extend" our \(y\) vector from a length \(0\) vector to a length \(n\) vector. And here's how: instead of writing \(y(k)=0\), \(y(k)=x(k)^2\) and \(y(k)=x(k)^3+2\), we could have respectively written \(y=[y,0]\), \(y=[y,x(k)^2]\) and \(y=[y,x(k)^3+2]\). Make sure that you understand why that works. Remember: it's MATLAB, if you wanna know how something works, just type it into the console and see what happens!

And there's an even "better" way of drawing these vectors without using if and for loops, which is very natural to MATLAB. It does have the slight disadvantage in that for the program that we wrote, we can increase the resolution of our graph by changing the parameter \(r\) in \(x=-3:r:3\) to be something smaller/finer. And the method that I'm about the describe is a tiny bit messier in this regard. But yea...the idea is that we can just produce the vector \(y\) "directly":

x1=-3:0.1:-2.1;
y1=0*x1;
x2=-2:0.1:-0.1;
y2=x2.^2;
x3=0:0.1:3;
y3=x3.^3+2;
x=[x1,x2,x3];
y=[y1,y2,y3];
plot(x,y,'+')

In fact, we could probably shorten all of that into just three lines, but I don't have MATLAB with me right now and I can't check if what I wanted to write down makes any sense. You guys should totes try to condense it to three lines though!

*: conclusion: Rabbis are the win! Respect ++. =P
**: having read that sentence, you now know how it feels.