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:
- 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.
- 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\).
- 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
- 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\).
- 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\).
- 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.
- 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\).
- 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\).
- 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\).
- 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\).
- Ends our if-loop.
- 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.
- Uses the plot-function native to MATLAB to draw our points on a plane.
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!
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.
No comments:
Post a Comment