Proof of Strong Induction Using Well-Ordering Principle Context: I keep running into circular reasoning in attempting to derive strong induction (more generally "induction" whether it be weak or strong) from the well-ordering principle. Assume:

  Peano Axioms w/ Well-Order: (I realize these are presented semi-informally)

  (P1) $\ \exists x[x\!=\!1]$;
  (P2) $\ $there exists an unary ("successor") function $S$ on $\mathbb{N}$ (i.e., $x\!\in\!\mathbb{N}\rightarrow S(x)\!\in\!\mathbb{N}$);
  (P3) $\ \forall x[S(x)\!\neq\!1]$;
  (P4) $\ \forall x\forall y[x\!\neq\!y\rightarrow S(x)\!\neq\!S(y)]$
  (P5') $\ $Well-Ordering Principle: Every non-empty set includes a least-element: $$ \forall B\Big[\emptyset\!\subset\!B\!\subseteq\!\mathbb{N}\longrightarrow\exists m\big[m\!\in\!B\wedge\forall p[p\!\in\!B\rightarrow m\!\leq\!p]\big]\Big] $$
  Note: Since I am trying to show the logical equivalency between Induction and the Well-Ordering Principle, I am assuming the latter as an axiom and treating the former as a theorem (below). The relation $\leq$ used above is defined next.

  Order Relation

  (O1) $\ x\!<\!y\leftrightarrow\exists z[x\!+\!z\!=\!y]$
  (O2) $\ x\!\leq\!y\leftrightarrow[x\!=\!y\vee x\!<\!y]$

  Addition (since order above is defined with "$+$")

  (A1) $\forall x[S(x)=x+1]$
  (A2) $\forall x\forall y[x+S(y)=S(x\!+\!y)]$

With this as background, below is the theorem and proof I see most often (or some variation thereof) in textbooks and online forums.

  Theorem: The Well-Ordering Principle (P5') implies the Strong Induction Principle.

  Proof: Suppose $X\!\subset\!\mathbb{N}$ with: (1) $1\!\in\!X$, and (2) $\forall x[x\!<\!k\rightarrow x\!\in\!X]\rightarrow k\!\in\!X$. Assume $X'\!\equiv\!\mathbb{N}\setminus X$ is non-empty. From Well-Ordering Principle (P5'), $X'$ includes a least element $m$. From (1), $m\!\neq\!1$. Since $m$ is the least element of $X'$, then all $x\!<\!m$ must belong to $X$. However, property (2) implies that $m\!\in\!X$, a contradiction. Thus, $X'$ must be empty and $X\!=\!\mathbb{N}$.

My problem is with the highlighted sentence above, which appears to me to require the result that $\neg(m\!\leq\!x)\leftrightarrow x\!<\!m$, which I believe is based on the Trichotomy Property (exactly one of $x\!<\!y$, $x\!=\!y$, $x\!>\!y$ holds). However, the only proof of the Trichotomy Property (that I am aware of) based on the above axioms/definitions alone uses Induction (see Thm 4.1c). Thus, it appears the reasoning is circular (induction is used to prove an intermediate result that is then used to prove induction).

Question: Assuming my understanding above is correct, my question simply put is this: does a proof exist of the Trichotomy Property for $<$ as defined above that does not require a proof based on induction?

The axioms you listed (P1-P5') are not equivalent to Peano's.  Replacing the (weak) induction axiom with the well-ordering axiom gives a weaker theory.  The well-ordered sets that are not order-isomorphic to the natural numbers still obey the well-ordering axiom.

Before I come back to the trichotomy question, let's recall the role of induction in Peano's axioms.  Like all the other axioms, induction is chosen so that the resulting theory may describe as well as possible the natural numbers.  Induction, specifically, is there to exclude certain undesirable models.

For instance, without induction, one could easily build a "non-standard" model of arithmetic that, besides the natural numbers, contained two more elements, call them $\alpha$ and $\beta$, such that $s(\alpha) = \beta$ and $s(\beta) = \alpha$.  Such a model would satisfy P1-P4, but induction rules it out.

If Peano's axioms included strong induction instead of weak induction, the resulting theory would allow models whose order type is not $\omega$.  For instance, $W = \{0,1\} \times \mathbb{N}$, with lexicographic ordering, satisfies P1-P5'.  (In particular, it is a well-order.)

On the other hand, weak induction does not "work" on $W$, because starting from $(0,0)$, which is the least element of $W$, and working up to $(0,1), (0,2)$ and so on, one never reaches $(1,0)$.  One could "prove" by weak induction that all elements of $W$ have first component equal to $0$.  For $W$ one needs transfinite induction, which is essentially strong induction.

Now, for the trichotomy property.  Note that Mendelson introduces $x < y$ as a "purely abbreviational definition" in terms of $+$. Therefore, $<$ must be proved a total order.  For that, induction is used; specifically, to show that the trichotomy property holds.

When proving that a well-ordered set satisfies the strong induction principle, the ordering of the set is supposed to be given, and to be a strict total order.  No property of strict total orders needs to be proved.

Much thanks to @Fabio for providing the answer which (after some slow thinking on my part and patience on @Fabio's part) led to my understanding of this problem.  It helped in my understanding to further write out the exemplary counterexample with the detail filled in (in particular, completing the definition of the addition operation), which I felt may be helpful to others to duplicate here.

  Theorem The "Well-Ordering Principle" identified as (P5') above does not imply induction.

  Proof: A counterexample satisfying (P1)-(P5') (where P5' is defined by (O1)-(O2) and (A1)-(A2)) is provided that does not satisfy the induction principle. Let $W$ be defined as the union of two systems of natural numbers $\mathbb{N}_a$ and $\mathbb{N}_b$. Next, the binary operation of "addition" can be defined on $W$ as follows:
  $$(A1)\ \ \forall x[x+1_a=S(x)]$$
  $$(A1_b)\ \ \left\{\begin{array}{l}\forall x\!\in\!\mathbb{N}_a[x+1_b=1_b] \\ \forall x\!\in\!\mathbb{N}_b[x+1_b=x] \end{array}\right.$$
  $$(A2)\ \ \forall x\forall y[x+S(y)=S(x+y)]$$
  The order relations $<$ and $\leq$ are defined as above in (O1) and (O2). So, for example, $7_a<3_b$ because $\exists z[7_a+z=3_b]$; in particular, $z=3_b$: $$7_a\!+\!3_b\!=\!7_a\!+\!S(2_b)\!=\!S(7_a\!+\!2_b)\!=\!S(7_a\!+\!S(1_b))\!=\!S(S(7_a\!+\!1_b))\!=\!S(S(1_b))\!=\!S(2_b)\!=\!3_b.$$
  In this sense, all $x\!\in\!\mathbb{N}_a$ are "less than" those $y\!\in\!\mathbb{N}_b$. Since $\mathbb{N}_a$ alone satisfies the induction principle, but $\mathbb{N}_a\neq W$, then (P5') does not imply induction.

  Trichotomy: One further point can be made--the trichotomy property does not hold for $W$ for the order defined by (O1)-(O2). For example, $1_b=1_b$ (implicit equality axioms what are part of the logical axioms). But from ($A1_b$), it also follows that $1_b+1_b=1_b$, which means $1_b<1_b$ (from (O1)). So $<$ is not trichotomous in this example.

So in conclusion, I think careful attention needs to be paid when one sees the statement that the "Well-Ordering Principle" is logically equivalent to "Induction" (I believe seen throughout the literature; but see, e.g., here). I think a more accurate statement would be: The Well-Ordering Principle (where the order relation is trichotomous) is logically equivalent with Induction.


How would I prove that these two expressions are equivalent? I want to figure out a way to simpilfy

$$x* \frac{1-\frac{|0-x|}{0-x}}{2}$$

to show that it is the same as

$$\frac{x+|x|}{2}$$

Or go the other way around and complicate the second equation so that it looks the same. I've been having trouble figuring out how to manipulate the 0-x that is inside the absolute value.

I get about this far then am not sure how to continue.

$$\frac{x-\frac{|-x^2|}{-x}}{2}$$

background context:

I needed an equation that took a number and set all the negative values to 0. I've already created a function in the past that took any number, and set the value below a certain threshold to zero:

$$x* \frac{1-\frac{|t-x|}{t-x}}{2}$$

where t is the threshold. So I could put in like 17 and anything less than 17 would be set to 0.

But I knew since the threshold in this case was 0 that probably meant I could cancel a bunch of stuff out and simplify the function. Then someone I work with offered the second function. And after checking the logic, it does have the exact same behavior or setting all negative numbers to be 0.

My equation tries to set the number to either 1 or -1, then shifts it over to be 2 or 0, cuts it in half to be 1 or 0, then multiplies by the original value.

Their equation is just set the number to 2x if it's positive, or 0 if it's negative. Then divides by 2 to get the original value, or it'll stay stuck at 0.

I was wondering if there were any edge cases where these two equations provided different answers, and want to practice math a bit. But still pretty bad at knowing all the algebra rules out there for simplification.


Prove that $V$ is not a free module. I am attempting to solve this:

  Let $R=\mathbb{Z}[\sqrt{-5}]$, and let $V$ be the R-module presented by the matrix $\begin{bmatrix} 2 \\ 1+δ \end{bmatrix}$ where $δ=\sqrt{-5}$. Prove that $V$ is not a free module.

Note on definitions

I want to note that my professor defines ($V$ is a free R-module) $\iff \exists k\in\{1,2,...\}[V\cong R^k]$. He also considers the empty set to NOT be a valid basis. So there is no basis for the trivial vector space. I know that these definitions are controversial, but bear with me for now.

My attempted solution

Let $T=\begin{bmatrix} 2 \\ 1+δ \end{bmatrix}R$. We know already $V\cong R^2/T$.

Assume $V$ is a free module. We want to obtain a contradiction.

Now, I see that the rank of $\begin{bmatrix} 2+P \\ 1+δ+P \end{bmatrix}$ (when $P$ is a prime ideal of $R$) can be either $0$ or $1$, depending on $P$. My professor says that the rank being non-constant contradicts the fact that $V$ is free, but alas, I do not see the contradiction.

For any maximal ideal $P\subset R$, consider $V/PV$, which is an $R/P$-vector space.  If $V$ were isomorphic to $R^k$, then $V/PV$ would be isomorphic to $R^k/PR^k\cong (R/P)^k$, so it would have dimension $k$ as an $R/P$-vector space.

But now note that $V/PV$ is presented as an $R/P$-vector space by the matrix $\begin{bmatrix} 2+P \\ 1+\delta+P \end{bmatrix}$.  So if $V/PV$ has dimension $k$, that matrix must have rank $2-k$.  In particular, if $V$ is free, the rank of $\begin{bmatrix} 2+P \\ 1+\delta+P \end{bmatrix}$ would have to be the same for all $P$.  Since this is not true, $V$ cannot be free.

To prove that $V/PV$ is presented as an $R/P$-vector space by the matrix $\begin{bmatrix} 2+P \\ 1+\delta+P \end{bmatrix}$, first consider the following general situation.  We have a module $M$ with submodules $N,K,$ and $L$ with $K,L\subseteq N$.  Note then that $$(M/K)/(N/K)\cong M/N\cong (M/L)/(N/L).$$  To apply this here, let $M=R^2$, $K=PM$, $L=\begin{bmatrix} 2 \\ 1+\delta \end{bmatrix}R$, and $N=K+L$.  Then $(M/K)/(N/K)$ is the quotient of $(R/P)^2$ by the subspace generated by $\begin{bmatrix} 2 + P \\ 1+\delta + P \end{bmatrix}$; that is, it is the $R/P$-vector space presented by the matrix $\begin{bmatrix} 2 + P \\ 1+\delta + P \end{bmatrix}$.  On the other hand, $(M/L)/(N/L)$ is $V/PV$.

Hint: There is a standard example of failure of unique factorization in $\mathbb{Z}[\sqrt{-5}]$.  Maybe you can adapt that?

Blunter Hint:

   What's $(1+ \delta)(1- \delta)$.  Is that also divisible by the other element of the presentation matrix?

Bazooka hint:

    The quotient is generated by the images of the standard basis elements in $R^2$ under the projection onto the quotient.  Free things don't have relations and $\begin{pmatrix}1 \\ 0\end{pmatrix} \cdot 2 + \begin{pmatrix}0 \\ 1 \end{pmatrix} \cdot (1 + \delta) =0$.  So this is not a free module on two generators.  Consequently, if it is a free module on one generator, it is generated by one of these.  Call these $e_1$ and $e_2$.  Keep adding copies of $e_1$ to the equation until you realize there's a multiple of $e_1$ that is a multiple of $e_2$ that is a multiple of $e_1$, i.e., $e_1$ satisfies a relation...  (Prior hints might shorten this search a bit.)


Conceptually, why does $e^{i\phi}$ describe a rotation? I've never understood conceptually why $e^{i\phi}$ describes a rotation by parameter $\phi$. I've seen this several times, mostly for more abstract objects like $e^{itA}$ where $A$ is an operator, I was always told it creates a rotation but I've never understood why.
If someone could explain this to me for the basic case $e^{i\phi}$ where $\phi\in\mathbb{R}$, then that would be really great, I can just generalize that concept to operators if I understood it.
As a side note, for the operator case, considering Stone's Theorem I can understand how unitary operators describe rotations (because the norm doesn't change, so it must just rotate the vector), but however I still don't understand conceptually how $e^{itA}$ would describe a rotation.

If $\phi\in\Bbb R$ then the map$$\begin{array}{rccc}r\colon&\Bbb C&\longrightarrow&\Bbb C\\&z&\mapsto&e^{i\phi}z\end{array}$$is a rotation of angle $\phi$ around the origin. That's so because $e^{i\phi}=\cos(\phi)+\sin(\phi)i$ and because, if $x,y\in\Bbb R$,\begin{align}r(x+yi)&=(\cos(\phi)+\sin(\phi)i)(x+yi)\\&=\cos(\phi)x-\sin(\phi)y+\bigl(\cos(\phi)y+\sin(\phi)x\bigr)i\end{align}and the map$$\begin{array}{ccc}\Bbb R^2&\longrightarrow&\Bbb R^2\\(x,y)&\mapsto&\bigl(\cos(\phi)x-\sin(\phi)y,\cos(\phi)y+\sin(\phi)x\bigr)\end{array}$$is a rotation of angle $\phi$ around the origin.

This is obvious, using Euler's formula: $e^{i \phi} = sin \phi + i sin \phi$, since the right side describes a point on the unit circle in the complex plane.
However, I think what you are asking about is perhaps about the intuition behind Euler's formula. The standard proof is based on the observation, that the Taylor expansions of both sides turn out to be the same, as answered here: Intuition behind euler's formula, but I don't think it is intuitive at all. So, this is only a sort of semi-answer; perhaps others more knowledgeable can give a better answer?
Euler's formula was based on an earlier result by Roger Cotes, who according to Wikipedia gave a geometric argument, but I haven't been able to find it.


Different shapes made from particular number of squares Good day! I’m currently investigating how different shapes can be made from a particular number of squares.
I have two major concerns: (1) Will there be a formula predicting the number of shapes that can be made from a certain number of squares without the flipping and rotation of formed shapes; and (2) how about with flipping and rotation?
Researching and manually listing the possible shapes that can be formed, my observations are the following:

Without flip and rotation:

Number of squares   -Number of shapes made

1- 1

2- 1

3- 2

4- 5

5- 12

6- 35

7- 108

8- 384 edit: should be 369

With flip and rotation:

Number of squares- Number of shapes made

1- 1

2- 2

3- 6

4- 19

5- 63

6- 208 edit: should be 216

Any help you might extend will be highly appreciated.

PS. Will really, really be grateful if you can provide an explanation why there is (or there is no) formula that can be derived from this.

Many thanks!

Edit: Added a picture because I don't think I was able to point my message clearly :D

When you have such a list of integers, it's always worthwhile to search for it in the Online Encyclopedia of Integer Sequences. The two sequences you describe are OEIS sequence A000105 and OEIS sequence A001168, though it seems you got the last counts wrong and they should be $369$ and $216$, respectively.

See also MathWorld and Wikipedia on polyominoes. According to the MathWorld article, not even the growth rate is known, so no formula is known for these numbers. As to your question why this is so, that's rather hard to answer specifically. Many mathematical problems prove intractable.

I thought of this question from playing blokus, and I thought I came up with an equation that works, but it only works for 1-5 pieces. I thought it was right since blokus doesn’t have pieces any larger than that. Here it is anyway though! For y= the size and x= number of pieces, $y=2^{(x-1)}-x+1$


Why does $y = x\sin(\frac{180}{x})$ approach $\pi$? A few days ago I was playing on my scientific calculator and I ran over an interesting little equation: $180\sin(1)$ is extremely close to $\pi$. At first I thought it was a coincidence, but then I tried $360\sin\left(\frac{1}{2}\right)$ and it was closer to pi. So then I tried out $90\sin(2)$ and it was farther from $\pi$. So I came up with the equation $y = 180x\sin\left(\frac{1}{x}\right)$, which I then simplified to $y = x\sin\left(\frac{180}{x}\right)$. Although it approaches $\pi$ slower (180 times slower), it is easier to understand what was going on on the desmos graphing calculator. It seems the larger the $x$ value, the closer it gets to $\pi$. I would like to know why exactly this happens.

EDIT: (Sine is in degrees not radians, just for clarification)

Given that you are still using degrees for trig functions, I am not sure how familiar you are with calculus. But I will try to explain what's happening without  calculus, and then show what happens with calculus.

As $x$ gets larger, it will cause your equation $y$ to increase. At the same time, the argument inside of $\sin$ is getting very small because you are dividing by $x$. When $\sin$ is evaluated near zero, the output will also be very near zero. You may have seen before that $$\sin(\theta) \approx \theta$$ when $\theta$ is small. Anyway, long story short, you are observing a mathematical battle where one part of the functions wants to diverge to infinity, and it is being multiplied by another part of the function that is tending toward zero. As you have noticed, the battle will balance out at $\pi$ in this particular case. Once you know (more) calculus, you will have tools to measure just how fast functions are growing or shrinking, and can evaluate limits like these. One useful tool is known as "L'Hospital's Rule" , which when applied to your function would say that $$lim_{x \rightarrow \infty} \left[x \cdot \sin\left(\frac{180}{x}\right)\right]$$ $$=lim_{x \rightarrow \infty} \left[\frac{ \sin\left(\frac{180}{x}\right)}{x^{-1}}\right]$$ $$=lim_{x \rightarrow \infty} \left[\frac{ \cos\left(\frac{180}{x}\right)\cdot \frac{-180}{x^2}}{-x^{-2}}\right]$$ $$=lim_{x \rightarrow \infty} \left[180\cos\left(\frac{180}{x}\right)\right]$$ Now you can argue that since $lim_{x \rightarrow \infty}\frac{180}{x}=0$ and $\cos(0)=1$ that $lim_{x \rightarrow \infty}\cos\left(\frac{180}{x}\right)=1$. So $$lim_{x \rightarrow \infty} \left[180\cos\left(\frac{180}{x}\right)\right]=180 \cdot 1=180$$ And since $180$ degrees is the same as $\pi$ radians, we have shown mathematically just what you have witnessed on your calculator.

EDIT: @Rodolvertice If you are interested in more limits like these, I will say that I think a very cool result comes from $$\lim_{x \rightarrow \infty} \left[\left(1+\frac{1}{x} \right)^x\right]$$

So I came to the same conclusion once, that as "x" approaches infinity, then the value "xSin(180/x)", in degrees, approaches pi. But I had a more deliberate approach at this the first time I figured it out.

It's quite simple... I treated every other regular polygon as we treat a circle... so that they too would have constants, as "pi" is to a circle... deriving a formula that would relate the number of sides of the polygon "n" and the longest distance from the center of the polygon "D" to the polygon's perimeter "C".Just as is "C = (pi)D".

I then ended up with "C or P = [nSin(180/n)]D". So that the constant of the shape "k" = "nSin(180/n)". I thought that, by logic, this SHOULD approach pi as "n" approaches infinity.
It gave me this graph enter image description here

So you can see that when you calculate "xSin(180/x)", your value of "x" is actually the number of sides of that regular shape... and as "x" approaches infinity, i.e. infinite sides of circle, you get (pi).

You could actually try and play around to get to the same conclusion I did. It's pretty correct. I hope this helps :)


Variables as arguments of exponential function make equation not linear? A Linear Algebra textbook I'm reading says the equation $$e^{x+y+z}=1$$ is not linear because x, y, and z are arguments of the exponential function. But I believe taking the natural log of both sides makes this $$x+y+z=\ln(1)$$ which is linear. Why isn't the first equation linear?

An equation in $x,y,z$ is linear  if it has the form $$ax+by+cz=d.$$Period. The equation $e^{x+y+z}=1$ is not of that form, so it's not linear.

It's equivalent to the linear equation $x+y+z=0$, but it's not the same equation.


Suppose that events $A$, $B$ and $C$ satisfy $P(A \cap B \cap C) = 0$ and each of them has probability not smaller than $\frac{2}{3}$. Find $P(A)$. Suppose that events $A$, $B$, and $C$ satisfy $P(A \cap B \cap C) = 0$ and each of them has probability not smaller than $\dfrac{2}{3}$. Find $P(A)$.

I don't understand this statement:

  $A \cap B$, $B \cap C$ and $C \cap A$ are (pairwise) disjoint events. Therefore, the sum of their probabilities is the probability of their union which cannot be greater than $1$.

Why is the sum of the probability of these three pairwise disjoint events $\leq 1$? shouldn't the probability of their union be $0$ such that the sum of their probabilities is not greater than zero? Please explain thanks.

  Solution: From the inclusion-exclusion formula
  $1 \geq P(A \cup B \cup C) = P(A) + P(B) + P(C) − P(A \cap B) − P(B \cap C) − P(C \cap A)$, hence $P(A \cap B) + P(B \cap C) + P(C \cap A) \geq 1$. But $A \cap B$, $B \cap C$ and $C \cap A$ are (pairwise) disjoint events. Therefore the sum of their probabilities is the probability of their union which cannot be greater than $1$. This means that we have equality everywhere, in particular, $P(A) = \dfrac{2}{3}$.

Simpler:

Consider the complements $A'$, $B'$ and $C'$, of $A$, $B$ and $C$, then $P(A'\cup B'\cup C')=1$ while $P(A')\leqslant\frac13$, $P(B')\leqslant\frac13$, and $P(C')\leqslant\frac13$ since $P(A)\geqslant\frac23$, $P(B)\geqslant\frac23$, and $P(C)\geqslant\frac23$.

Since $P(A'\cup B'\cup C')\leqslant P(A')+P(B')+P(C')$, this implies that $P(A')=P(B')=P(C')=\frac13$.

In particular, $P(A)=\frac23$.


Logic: Can you drop parentheses in a conjunction? In propositional logic, $p \land (q \land r) = (p \land q) \land r$ , where $p, q$ and $r$ are propositions.

Does this mean $p \land (q \land r) = p \land q \land r$ ? If so, why?

Yes, you are right: conjunction is associative. Thus, it doesn't matter where you put the parentheses. Hence, when you see "$p \land q \land r$", it means that you may insert the parentheses anywhere and you will get the same result.

Informally, one might say that if three things are true ($p \land q \land r$), then also one thing and two things — $p \land (q \land r)$ — and two things and one thing — $(p \land q) \land r$ — are true.

In a formal deductive system commonplace in symbolic logic, we want to be more formal. We usually deduce consequences from a set of premises. For example we deduce $p \land q$ from the set $\{p, q\}$. This is written:
$$\{p,q\} \vdash p \land q$$
where the braces are usually omitted, and $\vdash$ is voiced proves. Similarly:
$$p \land q \vdash p \qquad\qquad p\land q \vdash q$$
(where the premises thus are considered singleton sets) because this is simply throwing information away.

If we now allow chains of deduction, then, one easily obtains:
$$\begin{align*}\{p,q,r\} &\vdash p \land q& \{p \land q, r\} &\vdash (p \land q) \land r\\
\{p,q,r\}&\vdash q \land r&\{p, q \land r\}&\vdash p \land(q \land r)
\end{align*}$$
and from the rightmost conclusion the so-called $\land$-elimination rules  easily allow deriving $p, q$ and $r$ again. Thus either of the parenthesized expressions corresponds exactly to the truth of the three letters $p,q,r$. Thus we say they're (provably) equivalent:
$$p \land (q \land r) \dashv\vdash (p \land q) \land r$$

Thus we have demonstrated that the following definitions of $p \land q \land r$ are all equally sensible:

As $p \land (q \land r)$;
As $(p \land q) \land r$;
By stating $p \land q \land r$ is true precisely when $p,q,r$ are all true.


How to show 2 spanning sets are equal? Suppose that $\{u, v, w\}$ is a linearly independent set of vectors in $\mathbb{R}^{50}$.
Show that Span$\{u, v, w\}$ = Span$\{u − v, u − 2v + w, v + w\}$.

I know that in order to do this, I need to prove that each span is a subset of the other. So far, I have: $A :=$ Span$\{u, v, w\}$ and $B := $Span$\{u − v, u − 2v + w, v + w\}$.
Then, I showed that:

$u-v = -1(u)-1(v)+0(w)$ so $b1 ∈ A$.
$u-2v+w = 1(u)-2(v)+1(w)$ so $b2 ∈ A$.
$v+w = 0(u)+1(v)+1(w)$ so $b3 ∈ A$.

Since any element $b$ in $B$ can be written as a linear combination of $b1, b2$, and $b3, B$ is a subset of $A$. I struggle with how to prove that $A$ is a subset of B, though. Guess and check is becoming very tedious.

Hint: solve some systems of linear equations to express each of $u, v, w$ as linear combinations of the second set of vectors.

It's easy to observe that $\mathrm{span}B \subseteq \mathrm{span}A$.

Let $\alpha=\{u,v,w\}$, $\beta=\{u-v,u-2v,v+w\}$.

The matrix for the change of coordinate from $\beta$ to $\alpha$ (we don't write from $\alpha$ to $\beta$ since it's more difficult) is

$$
[{\sf Id}]_\beta^\alpha =
\begin{bmatrix}
1 & 1 & 0 \\ -1 & -2 & 1 \\ 0 & 0 & 1
\end{bmatrix}.
$$

Observe that this matrix is invertible since it has linearly independent columns, so ${\sf Id}: \mathrm{span}B \to \mathrm{span}A$ is bijective.


unknown polynomial divided by $x^2(x-1)$, find the remainder. I took an exam today and there's a problem stuck in my head; I still can't figure out yet.

Here's the question (just the concept as I can't remember precisely).

An unknown polynomial divided by $(x-1)^2$ leaves the remainder of $x + 3$ (not sure about the number) and when this polynomial is divided by $x^2 $, it leaves $2x + 4$ (again, not sure about the number). From the given conditions, if this polynomial is divided by $(x-1)x^2$, what would be the remainder?

The solution as far as I figured out is this:

first, from the division of $(x-1)^2$, I got that $f(1) = 3$
in the same way from division of $x^2$, I got $f(0) = 4.$

I can write the polynomial as follows:

$f(x) = (x-1)(x)(x) g(x) + ax^2 +bx +c$

$ax^2 + bx + c$ is the remainder.  And to find $a,b,c$, I can use the conditions above, so I got $c = 4$ by substituting $x = 0,$ and I got $a+b+4 = 3$ by substituting $x = 1.$

This leaves $a + b = -1,$ and I can't figure out how to continue; please help.

Edit : I made a mistake $f(1)$ should be equal to $4$ and $a+b+c = 4$


Benford's law and voting in Georgia With Benford's law "the leading digits of the number found in real-world data sets" should make sense.  But this video
https://www.youtube.com/watch?v=DoF3WS42w3M&ab_channel=RobertA.Bonavito%2CCPA
claims that by applying Benford's law they can prove electoral fraud.

He claims that since Benford's law is "broken" in these graphs, it appears that there has been fraud committed, but I wonder if the artificiality of breaking things into counties and only having 156 of them violates the "naturally occuring" idea that is the foundation of Benford's Law.
I am curious why Benford's law does not seem to apply here.

Using his data for first digits, neither the Biden nor the Trump first digits are significantly different from what would be predicted by Benford's law.  Using R:
countyBiden <- c(47,40,16,21,7,9,9,5,5)
countyTrump <- c(43,36,12,15,9,17,9,9,9)
benford <- log10(2:10) - log10(1:9)
chisq.test(countyBiden, p=benford)
#
#         Chi-squared test for given probabilities
#
# data:  countyBiden
# X-squared = 12.601, df = 8, p-value = 0.1263
#
chisq.test(countyTrump, p=benford)
#
#         Chi-squared test for given probabilities
#
# data:  countyTrump
# X-squared = 11.231, df = 8, p-value = 0.189

That is even before considering whether Benford's law should apply here.

Did you check Bedford's law against the number of registered voters in Georgia first? Because if that's off then the votes will be off also.


Are there "simple" functions whose asymptotic behaviour is impossible to know? My question is

  Does exist a simple  function $f \colon A \subseteq \mathbb R \to \mathbb R$ such that it is impossible to know $\lim_{x \to \infty} f(x)$ ?

Of course there are a lot of function whose behaviour is not known; but what happens if we use only elementary functions (the rigourous definition of elementary function involves differential algebra, so let's just imagine a elementary function as a composition of exponentials, logarithms, rational functions and trigonometric functions)?.
More clearly the problem is:

  Is it possible to create some function (or sequence) "easy to define" for which is not possible to evaluate his asymptotic behaviour?

Edit: with "not possible to evaluate" I mean that the problem to evaluate $$\lim_{x \to +\infty} f(x)$$
is not decidible.

Consider a sequence defined as follows (also see here):

$a_1=1$

$a_{n+1}\in\{a_n,a_n+1\}$

$a_n=$ number if occurences of $n$ in the sequence.

The recurrence defined above implies

$a_n+1=a_{n+a_{a_n}}$ Eq. 1

Suppose that we assume a leading behavior with the form

$a_n\approx \alpha n^\beta$  Eq. 2

Plugging Eq. 2 into Eq. 1 and applying the binomial power expansion to the right side gives what turns out to be the correct leading behavior:

$\alpha=\phi^{1/\phi^2}$

$\beta=1/\phi$

$\phi=(1+\sqrt5)/2$

This, put into Eq. 2,  is indeed the correct leading behavior.  But ... the higher order correction terms coming from the binomial expansion are $O(1)$, hence cannot rise above the "noise" generated by the unit jumps in this sequence of whole numbers.  Therefore, the leading behavior cannot be expanded into a power series or refined in any other way using analytic functions.

Whatever you mean, the following function satisfies your request:
$$f(x)= \begin{cases} x & \mbox{ if the Riemann Hypothesis is true}\\
-x & \mbox{ otherwise}\end{cases}$$

Knowing the limit of this function is not impossible, but it's still hard, since it's equivalent on proving the Riemann Hypothesis.

If you want something actually impossible, substitute the Riemann Hypothesis with something impossible to prove, for example the Continuum Hypothesis.


Question regarding Context Free Grammar exercises I'm working on the exercises in "An Introduction to Formal Languages and Automata" 4th Ed textbook by Peter Linz. Since there are too few answers given in the back of the book, I  wasn't able to check my work confidently. Although they look like homework, they are actually not; I just want to master the material that I've read. On the other hand, I'm not seeking a complete solution, a hint would be more than enough. Any suggestion would be greatly appreciated. Many thanks in advance.

Note: This is Exercise 5.1 on page 133, 134, and 135.

I didn't understand which problems from the list you want to analyze, so let me make some general remarks.

CFGs are equivalent to a limited form of computer programming. Instead of writing down a grammar it is easier to understand a set of "subroutines" by which one can (in principle) reduce the problem to easier grammar construction subproblems which are further reduced to smaller problems until it is obvious that all necessary transformations are grammatically expressible in CFG form.  This is especially true when you care only about the possibility of expressing the language as CFG and not about finding the "best" grammar that constructs the language.

In solving CFG problems it is useful to imagine taking the string and un-building it --- reducing it to the empty string while conserving membership in the language.  Often this can be reversed into a procedure for building any word in the language.

Most of the problems in the list take an easily generated language and impose one linear equation or one linear inequality on the numbers of $a,b,c \dots$ in the string.  There will be a finite number of basic operations that preserve the value of a function like $3n_a - 5n_b + n_c$ and allow motion through the level sets of this function (such as adding 5 letters $a$ and 3 letter $b$'s, or three $c$ and one $a$, and so on). If there are additional requirements like $a^* b^* c^*$ where there is an ordering on the letters, the operations will involve inserting (or deleting) letters at consecutive positions, such as $ac \to aacccc$.  Most of the linearly constrained problems on the list can be done in this way if you consider that operations can be done in stages, by adding extra "clock" letters if necessary that keep track of the different phases of the algorithm, and are removed at the end of the process.

As for the first question 7(a), on taking a quick look at it, the grammar written by you generates the language containing b (S => T => Tb => T)

S -> aSb | T  T -> Tb | a | aa | aaa | epsilon

However, the one suggested below as in the text seems to not do so.

S -> aA | aaA | aaaA | epsilonA -> aAb | BB -> Bb | epsilon

Could the one in the text possibly be a mistake?


What equal installment of annual payment will discharge a debt which is due as 848 at the end of 4 years at 4% per annum simple interest? What equal installment of annual payment will discharge a debt which is due as Rs. 848 at the end of 4 years at 4% per annum simple interest?

The above question can be calculated by using the formula $$x= \frac{100P}{100n+\frac{n(n−1)r}{2}}$$ which gives the result $= 200$. My doubt is that $200 \cdot 4 = 800$. So when will the balance $848-800= 48$ be paid?

*you are forgetting the interest on the payments *

Assuming payments at the end of each year,

interest of 4% for 3 years will accrue for 1st 200 when payment is due,

for 2 years for 2nd payment , etc.

The formula you used was devised taking this into account.

You can check that exactly 48 interest would have accrued at time of payment, you have paid the dues fully !

I also had the same problemn.My peer told me that bank receive the first payment after 1 year, and THEY invest it at 4% interest. So they get 3 years of interest on that .The payment made at end of first year has 3 years to earn simple interest at 4% per year. So t will be 3 for that.

But why 3 years or why not 1 year.


Finding UMVUE, given complete and sufficient statistic Let $X_1,X_2,…,X_n(n≥3) $ be a random sample from Poisson(), where$ θ∈(0,∞)$ is unknown and let
$T=\sum _{i=1}^n X_i$
The UMVUE of $ e^{−2\theta}*\theta^3$ is
Since UMVMUE is a Complete Sufficient Statistics then
$E(ϕ(t))=e^{−2\theta}*\theta^3$
$\sum \phi(t)∗ \frac{e^{−nθ}*(nθ)^t}{t!}=e^{−2\theta}*\theta^3$
$\sum \phi(t)∗ \frac{(nθ)^t}{t!}=e^{−2\theta+n\theta}*\theta^3$
$\sum \phi(t)∗ \frac{(nθ)^t}{t!}=\sum \frac{(−2\theta+n\theta)^r}{r!}*\theta^3$
How do we proceed after this?

First, to use a standard notation, let's set
$$S=\sum_i X_i$$
and observe that $S$ is CSS, Complete and Sufficient Statistic.
Then let's construct an unbiased estimator for $g(\theta)=e^{-2\theta}\theta^3$
A very simple unbiased estimator is the following:
$$T=\mathbb{1}_{(X_1\cdot X_2=2)}$$
where it indicates that $T=1$ if $X_1\cdot X_2=2$ and it is zero elsewhere.
Immediately you can verify that $\mathbb{E}[T]=e^{-2\theta}\theta^3$
Now you can apply Rao-Blackwell theorem calculating
$$\mathbb{E}[T|S]$$
which is your UMVUE, given that $S$ is also complete.

$$\mathbb{E}[T|S]=\mathbb{P}[T=1|S=s]=\frac{e^{-2\theta}\theta^3\mathbb{P}[S=s|T=1]}{\mathbb{P}[S=s]}=$$
$$=\frac{e^{-2\theta}\theta^3\mathbb{P}\left[ \sum_{i=3}^n X_i=s-3\right]}{\frac{e^{-n\theta}(n\theta)^s}{s!}}=\frac{e^{-2\theta}\theta^3\cdot \frac{e^{-(n-2)\theta}[(n-2)\theta]^{s-3}}{(s-3)!}}{\frac{e^{-n\theta}(n\theta)^s}{s!}}=\frac{(n-2)^{s-3}}{n^s}\cdot\frac{s!}{(s-3)!}$$


How do I solve a confusing trig substitution? Hi I am trying to solve an integral problem that involves trig substitution. First I tried completing the square, which gave me $1/\sqrt{(x+3)^2+2^2}$. I know I am supposed to use $x = \arctan(\theta)$. Does that mean it should be:

$x + 3 = \arctan(\theta)$

$x = \arctan(\theta) - 3$

and then Integrate from there? I am not sure if this is a good way of thinking about this problem. I would appreciate any help!

So you are trying to find
$$I=\int\frac{dx}{\sqrt{x^2+6x+13}}=\int\frac{dx}{\sqrt{(x+3)^2+2^2}}$$
And your goal is to find the right substitution $$x+3=a\cdot\tan\theta$$
such that $$(x+3)^2+2^2=(a\tan\theta)^2+2^2=2^2(\tan^2\theta+1)=2^2\sec^2\theta.$$
It does not take much to show that $a=2$. Can you take it from here?

Note that $$x^2+6x+13 = (x+3)^2+4$$

Your correct substitution  is$$(x+3)=2\tan(\theta)$$

$$dx=2\sec^2(\theta)d\theta$$

$$(x+3)^2+4=4\tan ^2(\theta)+4 =4(1+\tan^2 (\theta)= 4\sec^2(\theta)$$

$$\sqrt {x^2+6x+13}=2\sec (\theta)$$

Will take care of the radical and the integral is manageable from here on.


Limit of this expression $ \lim \limits_{n\to \infty }\left( \frac{15n+7}{n \log\left( n\right) } \right) $ The limit $$ \lim \limits_{n\to \infty }\left( \frac{15n+7}{n \log\left( n\right) } \right) $$
Is it valid to do

$\frac{15 + 7/n}{\log n}$

which makes the numerator go to $15$ as the bottom goes to infinity, therefore the whole thing goes to $0$? How would I show more formally that this is true?

Holds the following
$$0\leq\frac{15n + 7}{n\log n}\leq \frac{15n + 7n}{n\log{n}}\leq\frac{22}{\log{n}}<\varepsilon$$ for $n>e^\frac{22}{\varepsilon}$ and arbitrary $\varepsilon$.

By letting $\varepsilon\to 0$ and squeeze theorem, we can conclude $$\lim_{n\to\infty}\frac{15n + 7}{n\log n}=0.$$

Yes it is fully valid that $\lim_{n \to \infty} \frac{15n +7}{n \log n} = \lim_{n \to \infty} \frac{15 +\frac{7}{n}}{ \log n}$, and hence the limit is $0$.

To prove this, note that $\lim_{n \to \infty} \frac{\frac{1}{n}}{\frac{1}{n}} =1$. So,

$\lim_{n \to \infty} \frac{15n +7}{n \log n} = \lim_{n \to \infty} \frac{\frac{1}{n}(15n +7)}{\frac{1}{n}(n \log n)} =  \lim_{n \to \infty} \frac{15 +\frac{7}{n}}{ \log n} = 0$.


Finding $\frac{ \mathrm{d}y}{ \mathrm{d}x}$ when given that $\sqrt{1-x^2} + \sqrt{1-y^2} ={a}(x-y)$ Finding $\frac{ \mathrm{d}y}{ \mathrm{d}x}$ when given that $\sqrt{1-x^2} + \sqrt{1-y^2} = a(x-y)$. $a$ is a constant.

I have the final answer, which is $$\frac{ \mathrm{d}y}{ \mathrm{d}x} = \sqrt{\frac{1-y^2}{1-x^2}}.$$
But I've only been able to get till $$\frac{ \mathrm{d}y}{ \mathrm{d}x} = \frac{a\sqrt{1-x^2}+x}{a\sqrt{1-y^2}-y}.\sqrt{\frac{1-y^2}{1-x^2}}.$$

How can the two terms be cancelled off? Thanks.

start with the defining equation and use difference of squares ...

$$  a(x-y) = \sqrt{1-y^2}+\sqrt{1-x^2}  $$

$$  a \frac{x^2-y^2}{x+y} = \frac{x^2-y^2}{\sqrt{1-y^2}-\sqrt{1-x^2}}  $$

$$  a (\sqrt{1-y^2}-\sqrt{1-x^2}) = x+y $$

$$  a \sqrt{1-y^2}-y =a\sqrt{1-x^2}+x $$

so

$$  \frac{a\sqrt{1-x^2}+x}{ a \sqrt{1-y^2}-y }=1 $$

Solve explicitly for $y$:

$y = \frac{a^2 x-2 a \sqrt{1-x^2}-x}{a^2+1}$.

Then take the derivative:

${d y \over d x} = \frac{a^2+\frac{2 a x}{\sqrt{1-x^2}}-1}{a^2+1}$

or

$-\frac{2 a \sqrt{1-x^2}}{a^2+1}-\frac{2 x}{a^2+1}+x$


Is it morally right and pedagogically right to google answers to homework? This is a soft question that I have been struggling with lately.

My professor sets tough questions for homework (around 10 per week).

The difficulty is such that if I attempt the questions entirely on my own, I usually get stuck for over 2 hours per question, with no guarantee of succeeding.

Some of the questions are in fact theorems proved by famous mathematicians like Gauss, or results from research papers.

As much as I dislike to search for answers on the internet, I am often forced to by time constraints if I even expect to complete the homework in time for submission. (I am taking 2 other modules and writing an undergraduate thesis too).

My school does not have explicit rules against googling for homework, so I guess it is not a legal issue.

However, it often goes against my conscience, and I wonder if this practice is counterproductive for my mathematical development.

Any suggestions and experience dealing with this?

Let me explain why I, and almost all faculty members I know, do not want students searching for homework problems online.

It destroys our ability to calibrate the course difficulty. Twenty hours of homework a week is very high for a math course; higher than I would expect from any course that was not promoted as a "boot camp" style course. Either you are falling behind the rest of the class, or other people are turning in much scantier work than you are, or everyone is googling the problems. The first two situations are obvious, and your professor should be adjusting to it. The last situation is invisible. We had an analysis course at MI last year pedagogically ruined because everyone kept solving the homework problems, so the professor kept increasing his pace, until an in class test revealed that no one was actually doing the homework themselves.
It forces us to use more obscure, and often not as good, problems. There are some fields where there are computations every student should do -- and, as a result, they are written up in books and online sources everywhere. It hurts my ability to design good problem sets if I can't put this fundamental problems on the problem set. Even in fields where there are not such key problems, there are often only so many ways to set up an example so that it is doable in a reasonable amount of time. If I can't use the examples which are already online, then I need to pick larger and stranger values for my parameters, which makes the problem set harder.
I do not believe that students will learn as much from reading a solution as finding it themselves; this is probably uncontroversial. Moreover, I think that hearing a solution from a classmate with whom you have been discussing the problem together is better than hearing it from a classmate who solved it separately; hearing it from a classmate is better than hearing it from a faculty member; and hearing it from a faculty member is better than reading it in a textbook or here on math.SE. I think that the more interactive and the less polished the presentation, the more you have to engage your own understanding to process and take in the answer. This is why I almost never leave full answers to questions that look like homework here; I think it is harmful.

Let me quote the policy I will have for the combinatorial representation theory course I will be teaching this Fall:

  Homework Policy: You are welcome to consult each other provided (1)
  you list all people and sources who aided you, or whom you aided and
  (2) you write-up the solutions independently, in your own language. If
  you seek help from other mathematicians/math students, you should be
  seeking general advice, not specific solutions, and must disclose this
  help. I am, of course, glad to provide help!

  I don't intend for you to need to consult books and papers outside
  your notes. If you do consult such, you should be looking for
  better/other understanding of the definitions and concepts, not
  solutions to the problems.

  You MAY NOT post homework problems to internet fora seeking solutions.
  Although I know of cases where such fora are valuable, and I
  participate in some, I feel that they have a major tendency to be too
  explicit in their help. You may post questions asking for clarification and
  alternate perspectives on concepts and results we have covered.

You should ask your professor for his or her policy, but I think that this is on the permissive side of what most math professors would write if they thought about a policy.

Write up your homework solutions in tex and cite your sources.  Soon the professor will want you to help with research.


Is syntactic consequence required to define semantic consequence? I have read quite a number of the questions on stack exchange to try to understand the relationships/differences between syntactic consequence, semantic consequence, and material implication.
For example in this post: https://philosophy.stackexchange.com/questions/10785/semantic-vs-syntactic-consequence, the definition of semantic consequence is given as Γ ⊨ φ says: sentence φ is true in all models of Γ. A similar definition is given here: https://math.stackexchange.com/questions/365569/whats-the-difference-between-syntactic-consequence-⊢-and-semantic-consequence-⊨. In particular that we have to have the entailed sentence be 'true'.
From this I am wondering does 'truth' in the definition of semantic consequence require the use of syntactic consequence? That is, do we first need the notion of syntactic entailment in order to define this semantic consequence?

Any sensible system of logic (e.g. propositional calculus or predicate calculus) is sound ($p$ the syntactic consequence of $\Omega$ implies $p$ is the semantic consequence of $\Omega$. That means that if something is provable (from a set of premises) then it must be true (assuming the premises are true). This seems necessary if proof is going to mean anything. The non-trival theorem is whether $p$ being the semantic consequence of $\Omega$ implies that $p$ is the syntactic consequence of $\Omega$. i.e. if something is true then it is provable. This is true for the propositional calculus with a finite set of premises. It requires the axiom of choice to prove it for propositional calculus with an infinite set of premises and, of course, it is not true for any formal system that includes arithmetic (as shown by Godel).


How many possibilities in tinyurl Looking at tinyurl, there is anywhere from 1 digit to 7 digits of I believe 36 choices (lowercase letters a to z and digits 0 to 9)

How do I calculate mathmatically the number of permutations of the string with 1 to 7 digits and 36 characters?

thanks,
Dean

The number of permutations (without replacement) of size $k$ on an alphabet of size $n$ is $n^k$. If you just need an approximate answer, the term $36^7$ is by far the largest, but if you want an exact answer, you can sum from $k=1$ to $k=7$.

I was just wondering the same thing.. Look up factorials - "The factorial $n!$ gives the number of ways in which $n$ objects can be permuted."

Given $26$ characters and $10$ numerals, $36!= 3.72\times 10^{41}$,  a fair sized number! Tinyurl can repeat characters,  which reduces the overall combinations.

I don't know if tinyurl does capital letters as well, but if they do then they aren't ever going to run out - $66!= 5.4\times 10^{92}$.


Is there a limit of $\cos(n!)$? I encountered a problem today to prove that $(X_n)$ with $X_n = \cos(n!)$ does not have a limit (when $n$ approaches infinity). I have no idea how to do it formally. Could someone help? The simpler the proof (by that I mean less complex theorems are used) the better. Thanks

I suspect that you have miscopied the problem, or your source has an error. I will argue that, while your statement is extremely likely to be true, we probably do not know enough to prove it.

Here is why. Suppose, hypothetically, that
$$\frac{1}{2 \pi} = \sum_{i \geq 0} \frac{d_i}{i!}$$
where all the $d_i$ are integers and, for $i$ sufficiently large, each $d_i$ is either $0$ or $1$. This is extraordinarily unlikely. However, if we knew how to prove that this didn't happen, we would probably know enough to show that every digit occurs infinitely often in the decimal expansion of $\pi$, and I believe that is an open problem. So, while this scenario is almost surely false, I don't think we know enough to prove that it is false.

Now, in this scenario,
$$\cos n! = \cos (n! 2 \pi \sum_{i \geq 0} \frac{d_i}{i!}) = \cos (2 \pi N + 2 \pi \sum_{i \geq n+1} \frac{d_i }{(n+1)(n+2) \cdots i})$$
where $N$ is a very large integer. By the periodicity of $\cos$, this is just
$$\cos (2 \pi\sum_{i \geq n+1} \frac{d_i }{(n+1)(n+2) \cdots i}).$$

Now, once $n$ is large enough that $d_i$ is $0$ or $1$ for $i$ larger than $n$, we have
$$\sum_{i \geq n+1} \frac{d_i n!}{i!} \leq \frac{1}{n+1} + \frac{1}{(n+1)^2} + \frac{1}{(n+1)^3} + \cdots = \frac{1}{n}.$$
So, in our unlikely scenario, $\lim_{n \to \infty} \sum_{i \geq n+1} \frac{d_i n!}{i!} =0$ and $\lim_{n \to \infty} \cos n! = 1$.

If I may try to extract some basic lessons here, questions about trig functions evaluated at integers almost always turn into questions about $\pi$. Often they can be resolved simply by noting that $\pi$ is irrational; occasionally it is important to show that $\pi$ is not well approximated by rationals and sometimes, as in this example, they turn into claims about $\pi$ which are beyond current knowledge. The key point is to work out what they are saying about $\pi$, and then find out whether that fact is known.

Exercise: Show that, for any $a$ between $-1$ and $1$, there is a $\theta$ such that $\lim_{n \to \infty} \cos (n! \theta)$ is $a$.

I tried the following approach where I assumed the limit existed and attempted to get a contradiction. However, the best I could do was to get the same answer as David above that if (in the extremely unlikely case that) the limit exists, it will be 1. I just wanted to make a record of the approach here in case someone sees any potential to this approach.

Since $x_{n+1} = \cos((n+1)n!)$, it can be written as a $(n+1)$th degree polynomial in $\cos(n!)$. Should the limit exist, it will be a fixed point of this polynomial. Using standard multiple angle formulas (found here for ex.), we can show that the limit if it exists should equal $1$.


Why some functions are not integrable? I know that certain functions are not integrable. Geometrically integration is finding the area under the curve of the graph of the given function. So, in another way why is it not possible to find the area under the curve in case of certain functions?

Well, well, well, this question actually can go really deep into the elementary ideas of integration, or, in general, finding the area under a curve.

1: The Old School Way - The Method of "Exhaustion"

In the ancient times, and especially during the period when mathematicians such as Eudoxus and Archimedes lived, the main way in which one could calculate the area between non-linear curves was the Method of Exhaustion. We will examine, in short, how would this work on calculating the area of a circle.

Let a circle $\mathcal{C}$ of radius $R$ and let two squares, $A_1A_2A_3A_4$ (red) and $B_1B_2B_3B_4$ (blue) such that $A_1A_2A_3A_4$ is inscribed in $\mathcal{C}$ and $B_1B_2B_3B_4$ is circumscribed to $\mathcal{C}$. Then, we have the following situation:

Now, the next step is to enclose the circle in some "tighter" canonical polygons. An easy construction is to construct the octagons that are induced from the two squares $A_1A_2A_3A_4$ and $B_1B_2B_3B_4$, as it is depicted in the following shape:

Then one can move a step forward to create a deca-exagon (16 angles canonical polygon) etc. It is clear the the red polygon is always underestimating the area of the circle and the blue polygon is always oversetimating it.

Now, it is relatively easy, using the know formulas for the area of canonical polygons, to prove that both the red and the blue area do converge to the area of the circle. However, since back then calculus was not something  "known" with the modern-day meaning (numbers were always treted as geometrical objects and not as abstract notions) they used the following form of Eudoxus' principle:

  Eudoxus' Principle: Given two quantities $A,B$, if, from the first quantity $A$ we substract a quantity $C$ that is larger that the half of $A$ and, then, from the remnant ($A-C$ in modern notation) we substract a quantity that is larger than it half and we continue this way, then, after a finite number of steps, the remnant quantity will be less than $B$.

So, in that framework, it was sufficient to prove that each construction of a new $2^n-$sided polygon was "cutting" more than half of the error - which can be proved, but has a long and tiring proof and, hence, is out of the spectrum of this answer. After that, "convergence" (this is a modern term; it was not used back then) was ensured. What was missing was to show that these two areas (blue and red) were both "converging" to the area of the circle. To do so (since calculus and, hence, limits, were unknown) an argument - again tiring, in the general case -  of double contradiction was used.

It is remarkable that, in the same way one could find the volume of the sphere and several other 3D shapes.

2: The Riemann-Darboux Way - Upper and Lower Sums

It is called Riemann Integral, however, in order to find the very solid geometric foundation of the notions of integral and integration we should investigate the so-called Darboux Upper and Lower Sums.

Let us consider a bounded function $f:[a,b]\to\mathbb{R}$ - boundedness is necessary for Rieman-integration; else, what would be the meaning of the area under that curve? Then, let a partition $\mathcal{P_n}=\{a=x_0<x_1<\dots<x_n=b\}$ of the interval $[a,b]$ and also let $m_k=\inf\limits_{x\in[x_k,x_{k+1}]}f(x)$ and $M_k=\sup_{x\in[x_k,x_{k+1}]}f(x)$, $k=0,1,\dots,n-1$. Then we define the lower, $L(f,\mathcal{P_n})$, and upper $U(f,\mathcal{P_n})$, Darboux sums for that partition and function as follows:
$$\begin{align*}
L(f,\mathcal{P}_n)&=\sum_{k=0}^{n-1}m_k(x_{k+1}-x_k)\\
U(f,\mathcal{P}_n)&=\sum_{k=0}^{n-1}M_k(x_{k+1}-x_k)
\end{align*}$$

Also, we give the following definition:

  Thinner partition: A partition $\mathcal{Q}$ is called thinner than $\mathcal{P}$ if:
  $$\mathcal{P}\subseteq \mathcal{Q}$$

Now, as we go forward to thinner partitions $\mathcal{P_k}$, with $k>n$, we say that $f$ is Riemann integrable if:
$$\lim_{k\to\infty}U(f,\mathcal{P_k})=\lim_{k\to\infty}L(f,\mathcal{P_k})=I\in\mathbb{R}$$
for every sequence of "decreasing" partitions (every partition of the sequence is thinner than every previous one).

Note now that, in this way, Rieman integration is "just" a more generalised implementation of the Method of "Exhaustion" that ancient mathematicians used. Instead of canonical polygons, we do use the polygons induced from the partition of $f$'s domain we choose and these polygons are, in a way inscribed and circmuscribed to that curve. Also, thinner partitions are, in a sense, the same thing as going form a canonical $n-$polygon to another canonical $m-$polygon, with $m>n$. Moreover, what we seek, in order to be able to say that a function is Riemann integrable, is for the two limits of the sequences of the estimations given by the Darboux sums do converge to the same number, which was also the wanted in the Method of Exhaustion, in spite of not being proved with modern day calculus but with "old-fashioned" - however, interesting - geometrical arguments.

So, to conclude, a function is not Riemann integrable exactly when the Method of Exhaustion cannot be applied to the curve that represents it graph.

However, this does not apply to Lebesgue integrability... (I don't feel this was the case the OP requested, however, I can extend to Lebesgue integration, if requested).

3: Appendix - Integration as infinite non-countable summation and the Heuristic Method of Archimedes

In a "palimpseston" (Παλίμψηστον) - a script written on parchement that has been scratched and re-wrtiten in a direction vertical to the previous one - that was found in the early 20th century in an orthodox monastery close to Constantinople, after a small "adventurous" trip and, eventually, the proper scientific investigation, it was found that, the original script was a letter that Archimedes had writen to Eratosthenes in which, among other things, he was explaining the way though which he could find the results he should prove, however, he notes that he does not consider this method to be a method of prooving his results, just a way to "get a felling" of what the goal is.

In one of his examples he describes the way he found the area of a parabolic part - see this article in wikipedia: https://en.wikipedia.org/wiki/Archimedes_Palimpsest - and at some point he mentions that the reason he cannot consider this a proof is that of using a "summation of segments over an interval of real numbers" - this is in modern terms, not the ones used by Archimedes! So, with respect to the historical frame, Archimedes was very close to the notion of infinite, non-countable summation that we give to the Riemann integral, nowadays.

I think this is more or less due to Banach-Tarski paradox, which shows a ball can be decomposed into a finite number of point sets and reassembled into two balls identical to the original one. This means we cannot define measurement (a conception rather related with integration) for every point set.


Cubic formula gives the wrong result (triple checked) I'd like to solve $ax^3 + bx^2 + cx + d = 0$ using the cubic formula.

I coded three versions of this formula, described in three sources:
MathWorld, EqWorld,
and in the book, "The Unattainable Attempt to Avoid the Casus Irreducibilis for Cubic Equations".

While I get identical results across all versions, these results are incorrect.

For example, for $a=1$, $b=2$, $c=3$, $d=4$,

I find incorrect roots:
$x_1 = -0.1747 - 0.8521i$,
$x_2 = 0.4270 + 1.1995i$,
$x_3 = -2.2523 - 0.3474i$.

The correct roots are:
$x_1 = -1.6506$,
$x_2 = -0.1747 + 1.5469i$,
$x_3 = -0.1747 - 1.5469i$

In case you're interested, the actual code is below.
Thank you for your help!

%% Wolfram version

Q = (3*c - b^2) / 9;
R = (9*b*c - 27*d - 2*b^3) / 54;

D = Q^3 + R^2;
S = (R + sqrt(D))^(1/3);
T = (R - sqrt(D))^(1/3);

x1 = - b/3 + (S + T);
x2 = - b/3 - (S + T) / 2 + sqrt(-3) * (S - T) / 2;
x3 = - b/3 - (S + T) / 2 - sqrt(-3) * (S - T) / 2;

%% Book version

omega1 = - 1/2 + sqrt(-3)/2;
omega2 = - 1/2 - sqrt(-3)/2;

p = (3*a*c - b^2) / (3*a^2);
q = (2*b^3 - 9*a*b*c + 27*(a^3)*d) / (27*a^3);

r = sqrt(q^2/4 + p^3/27);
s = (-q/2 + r)^(1/3);
t = (-q/2 - r)^(1/3);

x1 =        s +        t - b/(3*a);
x2 = omega1*s + omega2*t - b/(3*a);
x3 = omega2*s + omega1*t - b/(3*a);

%% Eqworld version

p = - 1/3  * (b/a)^2 + (c/a);
q =   2/27 * (b/a)^3 - (b*c)/(3*a^2) + d/a;

D = (p/3)^3 + (q/2)^2;
A = (-q/2 + sqrt(D))^(1/3);
B = (-q/2 - sqrt(D))^(1/3);

y1 = A + B;
y2 = - 1/2 * (A + B) + sqrt(-3)/2 * (A - B);
y3 = - 1/2 * (A + B) - sqrt(-3)/2 * (A - B);

x1 = y1 - b / (3*a);
x2 = y2 - b / (3*a);
x3 = y3 - b / (3*a);

The problem occurs when you are taking a cube root: in the Wolfram version, when you compute $$T = \sqrt[3]{R - \sqrt{D}} = \sqrt[3]{-\frac{35}{27}-\sqrt{\frac{50}{27}}}$$ and in corresponding places in the other versions of the cubic formula.

The expression inside the cube root is negative (approximately $-2.66$), and the cubic formula works if you take the real cube root (approximately $-1.39$). But writing $(R - \sqrt D)^{1/3}$ in many computer algebra systems instead computes the principal cube root: the complex root with largest real part. This will be the real cube root for a positive number, but here, it gives us approximately $0.69 - 1.2 i$, and that is the source of your error.

I can't identify the language you're using by looking at it, so I don't know what the best way to avoid this problem is. In Mathematica, there's a built-in CubeRoot command, which will always take the real root of a real number.

You can always make it go with some conditionals: define $T$ to be

$(R - \sqrt{D})^{1/3}$, if $R - \sqrt D \ge 0$, and
$-(\sqrt D - R)^{1/3}$, if $R - \sqrt D < 0$.

(And do a similar thing everywhere else you take a cube root.)

The above will work for real coefficients; for complex coefficients (or even when $D$ is negative), we want to be more careful, because then a real root might not exist.

The idea is that we ran into trouble here, not because we weren't taking the real root necessarily, but because we took two cube roots that "didn't match up with each other". We can rewrite the cubic formula in a few different ways so that we only take one cube root, and express the other cube root we'd have to take in terms of the first. Then the issue doesn't occur.

This gives us a better way to solve the problem in code: after computing $S = (R + \sqrt D)^{1/3}$, set $T = -Q/S$. The justification is this: since $S^3 = R + \sqrt D$ and $T^3 = R - \sqrt D$, we have $S^3 T^3 = R^2 - D = -Q^3$. Naively, we can cancel the cube roots and assume $ST = -Q$, and this works out.

See also this question and its answer.

This does not look right.

y2 = - 1/2 * (A + B) + sqrt(-3)/2 * (A - B);
y3 = - 1/2 * (A + B) - sqrt(-3)/2 * (A - B);

Did you mean cbrt(-3)?


How to prove $\displaystyle\lim_{z\to z_0}\dfrac{f(z)}{g(z)}=\dfrac{f'(z_0)}{g'(z_0)}$ How to prove the following

  $f, g$ are differentiable at $z_0$ with $f(z_0) = g(z_0) = 0.$ If $g'(z_0) ≠ 0$ then $\displaystyle\lim_{z\to z_0}\dfrac{f(z)}{g(z)}=\dfrac{f'(z_0)}{g'(z_0)}$

i agree with user39483 .its correct .he has taken the right hand side and used definition of derivative .then the denominators cancel out and given values are substituted .hence we get the left hand side ...now i dont know how to write z(naught) in computer so i will use m in place of z(naught)..........................................................................
LHS= lim(z--m) [f(z)/g(z)].....let z=m+h then as z--m then h tends to 0......= lim(h--0)[f(m+h)/g(m+h)]......now using the taylors theorem .....= lim(h--0) [{f(m)+hf'(m)+...+R1} / {g(m)+hg'(m)+...+R2}].....where R1 and R2 are remainders.....since f(m)=g(m)=0 therefore.....= lim(h--0) [ {hf'(m)+terms with higher powers of h} /{hg'(m)+terms with higher power of m}].....= lim(h--0) { h(f'(m)+terms with higher powers of h)} /{h (g'(m)+terms with higher powers of m)} ].....we took h common in previous step and now h cancels out and then we apply  limit.....= f'(m)/g'(m) .....=RHS..... if this solution is incorrect then i would like to know whats wrong with it.


Gödel's beta function, without the Chinese remainder theorem As we all know, Gödel's beta function exploits the Chinese remainder theorem to encode a finite sequence of naturals into a single natural.  This does not require a strong theory; it can be carried out in, e.g., the theory of discretely ordered semiring plus the $\Sigma_1$ induction.

While the CTR is by no means hard, it would be helpful to base your encoding of strings on a even more trivial number-theoretic facts, since there would be less chances you screw things up when you take an oral exam or you teach a class.

Question: Can one use even easier number-theoretic facts to encode finite sequence of naturals in a single natural?  The encoding and decoding has to be able to be done in the theory of discretely ordered semiring plus the $\Sigma_1$ induction.

See :

Raymond Smullyan, Theory of formal systems (1961), page 78:

  our proof follows novel lines in that all appeal to the traditional number theory devices accorded this in the past — e.g., prime factorization, congruences and the Chinese remainder theorem — are avoided. Thus Gödel's program of establishing  incompleteness, even of first order theories involving plus and times as their sole arithmetical primitives, can, by the methods of this section, be carried out without appeal to number theory.

What about replacing the string $a_n \dots a_0$ with the number $f(a_n \dots a_0)$ whose binary representation is obtained by replacing each $a_i$ in $a_n \dots a_0$ with $1$ followed by $a_i$ zeroes? This gives bijection I believe, with the empty string being sent to $0$. Defining $b_0$ as $0$ and $b_i$ as $\sum_{j = 0}^{i - 1} (a_j + 1)$ else, I think gives that $f(a_n \dots a_0) = \sum_{i = 0}^n 2^{a_i + b_i}$. Don't know whether the encoding and decoding is simple enough for your needs.


Let $f$ be a continuous and differentiable function such that $f(a)=f(b)=0$ , show that $f'(c)=\pi f(c)$ for some $c \in (a,b)$ Let $f:[a,b] \rightarrow \mathbb{R} $  be a continuous function in $[a,b]$ and differentiable in $(a,b)$   such that $f(a)=f(b)=0$ . Show that $f'(c)=\pi f(c)$ for some $c \in (a,b)$

The initial hypothesis of that $f(a)=f(b)$ makes me think that I need to use the Rolle's Theorem of some way but I don't see how to use it.

Any hint will be appreciated.

Define $g(x)=f(x)\cdot e^{-\pi x}$. Notice that $g$ is, like $f$, continuous on $[a,b]$, differentiable on $(a,b)$, and zero at the endpoints $a$ and $b$.  Also notice that $$g'(x)=f'(x)\cdot e^{-\pi x}+f(x)\cdot(-\pi)e^{-\pi x}= (f'(x)-\pi f(x))e^{-\pi x}.$$  Apply Rolle's theorem.

Consider the function g(x) = f(x)exp(-πx) .

Then g(a) = f(a)exp(-πa) =   0.exp(-πa) = 0
     g(b) = f(b)exp(-πn) =   0.exp(-πb) = 0
and note that the derivative g'(x) = f'(x)exp(-πx) - πf(x)exp(-πx)
so we can apply Rolle's theorem, so there exists c such that

 g'(c) = 0, f'(c).exp(-πc) - πf(c).exp(-πc) = 0

we can divide by exp(-πc) to give the result

   f'(c)  - πf(c)  = 0


Aligning an object's "down" vector to another vector in world space, for better rotation I have an object whose definition includes up, forward, and left vectors in both local and world space. I can also cause yaw, pitch, and roll rotational acceleration on the object, relative to its local space.

I'd like to align this object's "down" to another vector in world space.

I'm able to do this currently by taking the object's down world vector and the target vector, using these to get a rotation matrix, extracting a pitch and roll angle from that matrix, and using those angles to influence the object's rotational acceleration.

The problem I'm having is that, while the object does always reach the target orientation, it gets there via a wobbly, round-about way.

Is there a method to achieve a more direct re-orientation path?

(While I understand the concepts in a general, conceptual kind of way, I'm not strong on the math. Despite this, you can assume the rotational matrix and Euler angles are computed correctly as those are done via third-party software. I'm aware of quaternions and they seem like they might be used to solve my problem but I'm not sure if they'd help given the constraints.)

As I stated in the question, the controls are on the object and so apply to local space but I was using global space vectors to calculate the rotation. When the axis are misaligned between local and remote space, and you're updating over time, you'll eventually hit your target orientation but will take a round-about path to do it.

I think this is because, repeatedly applying rotations meant for global axis alignment to local space induces a sort of wandering but, as the the local and global axes start to align, the angles when comparing global and local start to match up.

This may also explain why some starting orientations would have more wandering than others. The global and local pitch and roll would only match up if the yaw also matched up. I suspect the wandering was more pronounced when the initial local yaw wasn't near a global yaw that lined up properly. The psuedo-Lissajous motion would cause yaw twisting, eventually aligning all three.


Convexity of Log-Sum-Exp Consider a matrix $A \in \mathbb{R}^{m \times n}$. Let $a_i^T$ be the $i^{th}$ row of $A$. Define $f(x) = \log \left( \sum \limits_{i = 1}^m \exp(a_i^Tx) \right)$ for $x \in \mathbb{R}^n$. I'm looking to show that $f$ is convex in its domain.

In particular, I'm hoping to use the second order characterization of convexity and show that $\nabla^2 f(x) \succcurlyeq 0$. I've written the gradient down as the $n$-dimensional vector $\nabla f(x)$, where the $j^{th}$ element (for $1 \leq j \leq n$) is given by $\frac{\sum \limits_{i = 1}^m a_{ij} \exp (a_i^Tx)}{\sum \limits_{i = 1}^m \exp (a_i^Tx)}$. However, I'm having trouble writing down the Hessian from this. I think it should be relatively easy then to show that for any non-zero $v \in \mathbb{R}^n$, $v^T\nabla^2f(x)v \geq 0$. How would I go about completing this proof?

I don't think proving its Hessian matrix is PSD to show the convexity of log-sum-exp function is a proper way. Analyzing the convexity of composite function may be more effective.

However, I still try to compute the Hessian matrix here. Let us reformulate the function
\begin{equation}
f(x) = \log(I^T \exp(Ax)),
\end{equation}
where $I \in \mathbb{R}^n$ is an all-one vector.
Then the gradient of $f$ is
\begin{equation}
\nabla f(x) = \frac{A^T \left(\exp(Ax) \circ I \right)}{I^T \exp(Ax)} = \frac{A^T \exp(Ax)}{I^T \exp(Ax)},
\end{equation}
which is actually the OP computed result.

And the Hessian matrix of $f$ is
\begin{equation}
\nabla^2 f(x) = \frac{A^T \operatorname{Diag}(\exp(Ax))A}{(I^T \exp(Ax))^2}.
\end{equation}
Due to $\operatorname{Diag}(\exp(Ax)) \ge 0$, the hessian matrix is PSD.


Complex vector space identity Let $A$ be an $n \times n$ complex matrix and let $u \in \mathbb{C}$ be a column vector. Suppose $u^*Au=0$ for all $u$.  What's the most straightforward way to see that $A=0$?

If one takes for $u$ the vector $\begin{pmatrix}x_1&\ldots& x_n \end{pmatrix}$ then the proposed equation becomes a quadratic form that is zero for all the values of the indeterminates $x_1, \ldots,x_n$ so its coefficients must  all be zero.

First, as suggested above, use $u$ as the basis vectors. This gives the diagonal elements, $A_{ii}$ must be zero. Next, use $u = \mathbb{1}$(vector of all ones). This gives $\sum_{i,j}A_{ij} = 0$. Using this with above fact you get $\sum_{i >j} A_{ij} + \sum_{i <j} A_{ij} = 0$. Finally, set $u = e_{i} + e_{j}$ where ${e_i}$ are canonical basis vectors to show that $\sum_{i > j}A_{ij}$ (or $\sum_{i < j}A_{ij}$) $ = 0$.


Find the greatest and least values of $(\sin^{-1}x)^2+(\cos^{-1}x)^2$ Find the upper and lower limit of

  $$
(\sin^{-1}x)^2+(\cos^{-1}x)^2
$$

My Attempt:

$$
\frac{-\pi}{2}\leq\sin^{-1}x\leq \frac{\pi}{2}\quad\&\quad0\leq\cos^{-1}x\leq\pi\\(\sin^{-1}x)^2\leq\frac{\pi^2}{4}\quad\&\quad(\cos^{-1}x)^2\leq\pi^2\\
0\leq(\sin^{-1}x)^2+(\cos^{-1}x)^2\leq\frac{\pi^2}{4}+\pi^2=\frac{5\pi^2}{4}
$$

Here, I can see the upper limit is $\frac{5\pi^2}{4}$ which is fine. But, $0$ is one lower limit not the lower limit.

Why am I not getting the lower limit in my approach ?

How do I approach similar problems involving max and min, when you don't get the lower or upper limits ?

Let $\sin^{-1}x=a,\cos^{-1}x=b$

$a+b=\dfrac\pi2$

$$a^2+b^2=\left(\dfrac\pi2-b\right)^2+b^2=\dfrac{\pi^2}4+2\left(b-\dfrac\pi4\right)^2-2\left(\dfrac\pi4\right)^2$$

Again , $0\le b\le\pi\implies0\le\left(b-\dfrac\pi4\right)^2\le\left(\pi-\dfrac\pi4\right)^2$


Does this table fit the normal distribution? The Pascal triangle can be described by the recurrence:

$P(n,1)=1, k>1: P(n,k) = P(n-i,k-1) + P(n-i,k)$

This well known triangle has the basic properties that the ratios of consecutive anti-diagonal sums (Fibonacci numbers) tend to the golden ratio, and that the ratios of consecutive row sums certainly tend to $2$.

By the central limit theorem, wikipedia quote:
"When divided by $2^n$, the nth row of Pascal's triangle becomes the binomial distribution in the symmetric case where $p = 1/2$. By the central limit theorem, this distribution approaches the normal distribution as n increases."

Another triangle with the same golden ratio - and consecutive rows sums ratio tending to $2$ properties, albeit with somewhat slower convergence, is the cumulative column sums of the Mahonian numbers with the recurrence:

$T(n,1)=1, k>1: T(n,k) = \sum\limits_{i=1}^{k-1} T(n-i,k-1)$

starting:

$\begin{bmatrix} 1&0&0&0&0&0&0 \\ 1&1&0&0&0&0&0 \\ 1&1&1&0&0&0&0 \\ 1&1&2&1&0&0&0 \\ 1&1&2&3&1&0&0 \\ 1&1&2&5&4&1&0 \\ 1&1&2&6&9&5&1 \end{bmatrix}$

Does this later table also by some argument fit the normal distribution as n gets large?

Arguments against this seems to be that the right-hand half of the table gets bigger and bigger while the left-hand side remains constant tending to the factorial numbers.

On the other hand by plotting the values of the first few rows it looks like a normal distribution.

Edit 4.2.2012:

The Mathematica 8 program for the table is:

Clear[T];
nn = 15;
T[n_, 1] = 1;
T[n_, k_] :=
 T[n, k] = If[n >= k, Sum[T[n - i, k - 1], {i, 1, k - 1}], 0]
MatrixForm[Table[T[n, k], {n, nn}, {k, nn}]]

Edit 20.10.2014:

Clear[T];
width = 20
height = 35000;
T[n_, 1] = 1;
T[n_, k_] :=
 T[n, k] = If[n >= k, Sum[T[n - i, k - 1], {i, 1, k - 1}], 0]
Table[ListLinePlot[Flatten[Table[T[n, k], {n, nn, nn}, {k, width}]],
   DataRange -> {0, width}, PlotRange -> {0, height},
   InterpolationOrder -> If[nn - 1 >= 11, 11, nn - 1]], {nn, 1,
   width}];
Show[%, ImageSize -> Large]

No. The second table isn't symmetrical about the center value in the row. The Pascal triangle has this property.

The function provided is sequence A179748. See: http://oeis.org/A179748

I'd also point out again that this is not the Mahonian numbers as has been pointed out in the comments. The Mahonian numbers are symmetric. The Mahonian numbers are sequence A008302. See:
http://oeis.org/A008302


how to calculate the following expression? Let $f$ be a smooth function and $\alpha >0$, i would like to know how to calculate the following expression: $$ A:=\dfrac{d}{dt}\left[\int_0^t f(s) \sin(\alpha(t-s))ds\right] $$
I followed a very simple method but i think that it is wrong.
I assumed that $$ \int_0^t f(s) \sin(\alpha(t-s))ds=G(t)-G(0) $$
where $$G(s)=\int g(s) ds$$ and $$g(s)=f(s)\sin(\alpha(t-s))$$
Then we have $$ A= \frac{d}{dt}\left(G(t)-G(0)\right)= g(t)=0$$
Question:

Did i make any mistakes ?

How to proceed to calculate this type of integral ?

Note that $t$ is also present in the integrand, so you need to apply the chain rule:
$$
\frac{d}{dt}\int_0^t g(t,s)ds=g(t,t)+\int_0^t ds \frac{d}{dt}g(t,s)\ .
$$
In your case, $g(t,t)$ is indeed equal to zero, but the second chunk is not...

$$ A:=\frac{d}{dt}\left[\int_0^t f(s) \sin(\alpha(t-s))ds\right] =$$
$$=\frac{d}{dt}\left[\sin(\alpha{t})\int_0^t f(s)\cos(\alpha{s}) ds-\cos(\alpha{t})\int_0^t f(s)\sin(\alpha{s}) ds\right]=$$
$$=\alpha\cos{\alpha{t}}\int_0^t f(s)\cos(\alpha{s}) ds+\alpha\sin{\alpha{t}}\int_0^t f(s)\sin(\alpha{s}) ds=$$
$$\alpha\int_{0}^{t}f(s)\cos{(\alpha(t-s))}ds$$


Solving $\frac{1}{|x+1|} < \frac{1}{2x}$ Solving $\frac{1}{|x+1|} < \frac{1}{2x}$

I'm having trouble with this inequality. If it was $\frac{1}{|x+1|} < \frac{1}{2}$, then:

If $x+1>0, x\neq0$, then

$\frac{1}{(x+1)} < \frac{1}{2} \Rightarrow x+1 > 2 \Rightarrow x>1$

If $x+1<0$, then

$\frac{1}{-(x+1)} < \frac{1}{2} \Rightarrow -(x+1) > 2 \Rightarrow x+1<-2 \Rightarrow x<-3$

So the solution is $ x \in (-\infty,-3) \cup (1,\infty)$

But when solving $\frac{1}{|x+1|} < \frac{1}{2x}$,

If $x+1>0, x\neq0$, then

$\frac{1}{x+1} < \frac{1}{2x} \Rightarrow x+1 > 2x \Rightarrow x<1 $

If $x+1<0$, then

$\frac{1}{-(x+1)} < \frac{1}{2x} \Rightarrow -(x+1) > 2x \Rightarrow x+1 < -2x \Rightarrow x<-\frac{1}{3}$

But the solution should be $x \in (0,1)$.
I can see that there can't be negative values of $x$ in the inequality, because the left side would be positive and it can't be less than a negative number. But shouldn't this appear on my calculations?

Note that $x$ cannot be negative as $|x+1|$ is always nonnegative.

With that mind, observe that $|x+1| = x+1, \forall x > 0$. Therefore

$$ \frac{1}{x+1} < \frac{1}{2x} $$

which results in $x < 1$ as you have done.

So the final result is $x \in (0,1)$

So from first case where $x\in(-1,\infty)$, you get the permissible via of $x$ to be $$(-1,\infty)\cap(-\infty,1)=(-1,1)$$

In the second case where $x\in(-\infty,-1)$ you get the permissible via of $x$ to be $$(\infty,-1)\cap\left(-\infty,-\frac13\right)=(-\infty,-1)$$


Question about the Definition of Differential Forms Question: Why does the definition of a differential form guarantee that when we do integration using differential forms, it is the same as the usual Riemann integral (before we introduce the concept of differential form)?

Example: If I want to prove Stoke’s Theorem, and I define the “differential form”, then the “differential form” may have certain rules of calculation. Then I use the “differential form” to prove the Stoke’s Theorem.

But why is Stoke’s Theorem in the form of “differential forms” is equivalent to the usual Stoke’s Theorem (which we learn in multivariable calculus) ?

" But why Stoke’s Theorem in the form of “differential form” is equivalent to the usual Stoke’s Theorem (we learn in multivariable calculus) ?"

I can answer this question.

Take the generalized stokes theorem:
$$\int\limits_{\partial M} \omega   = \int\limits_M {d\omega } $$
The multivariable calc version of stokes theorem relates the integral over a 2-manifold to an integral over its boundary so we will want to choose omega to be a 1-form.

We can make it: $$\omega  = {F_x}dx + {F_y}dy + {F_z}dz$$
We then take the exterior derivative:
$$d\omega  = d{F_x} \wedge dx + d{F_y} \wedge dy + d{F_z} \wedge dz$$
Recalling that $$d{F_x} = {{\partial {F_x}} \over {\partial x}}dx + {{\partial {F_x}} \over {\partial y}}dy + {{\partial {F_x}} \over {\partial z}}dz$$
and using the symmetry property of differential forms
$$d{x^i} \wedge d{x^j} =  - d{x^j} \wedge d{x^i}$$
We get
$$d\omega  = \left( {{{\partial {F_z}} \over {\partial y}} - {{\partial {F_y}} \over {\partial z}}} \right)dy \wedge dz + \left( {{{\partial {F_x}} \over {\partial z}} - {{\partial {F_z}} \over {\partial x}}} \right)dz \wedge dx + \left( {{{\partial {F_y}} \over {\partial x}} - {{\partial {F_x}} \over {\partial y}}} \right)dx \wedge dy$$

Now if you look at these results you should notice $$\omega  = \vec F \bullet d\vec r$$ and $$d\omega  = \nabla  \times \vec F \bullet d\vec A$$
Which gives us the multivariable calculus version of Stokes Theorem:
$$\int\limits_{\partial M} {\vec F \bullet d\vec r}  = \int\limits_M {\nabla  \times \vec F \bullet d\vec A} $$

I think is by definition.
Suppose that $\omega=f(x) dx$ then
$$\int_M w \overset{\mathrm{def}}{=} \int_M f(x) dx.$$
So, you have to demostrate that the other tools of differential form, i.e. $d$, wedge product, hodge operator etc match well with this definition of integral. An example of this proof is the above answer


Help proving that $(n+a)^b = \Theta(n^b)$ Please you apologize me by my English.

I don't know how make that:
$$(n+a)^b = \Theta(n^b), b > 0$$
I know, I must to find two constants such that:
$$ c_{1} n^b \leq (n+a)^b \leq c_{2} n^b $$

I do not know what else to do. I'v tried with the Newton's binomial, but I'm lost.

If $a \geq 0$ then

$$(n+0)^b \leq (n+a)^b \,,$$

thus $c_1=1$ works.

Also, for all $n \geq a$ you have

$$(n+a)^b \leq (2n)^b =2^b n^b \,.$$

Now, fixing

$$c_2 = \max \{ 2^b, \frac{(n+1)^b}{n^b},...,  \frac{(n+n-1)^b}{n^b} \}$$

you get the desired inequality.

For $a \leq 0$ you can get the inequlities the other way around, excepting that you'll have an issue if $a$ is a negative integer (what happens if $n=-a$?).

I proved it using the binomial expansion , which is

(x+y)n=nC0xny0+nC1xn−1y1+nC2xn−2y2+......nCnx0yn
now for the above problem (n+a)b=bC0nba0+nC1nb−1a1+nC2nb−2a2+......nCnn0an

we also now that for any polynomial
a0x1+a1x2+a2x2+⋯+anxn≤(a0+a1+a2+⋯+an)xn

substituting bC0a0
with C0, bC1a1 with C1

and so on (because that is a constant) we would get

(n+a)b=C0nb+C1nb−1+C2nb−2+......Cnn0

now i would jump to the following conclusion

C0nb≤C0nb+C1nb−1+C2nb−2+......Cnn0≤(C0+C1+C2+......Cn)nb

which makes (n+a)b=θ(nb)


Calculating the minimum cost trajectory between two points An airplane must travel from point $A$ to point $B$, both at zero altitude and separated
  from each other by a distance $d$. In this problem we assume that the surface of the
  Earth is actually a plane. An airplane costs more money to fly at a lower altitude than
  at a higher one. We wish to minimize the cost of a trajectory between the points $A$ and
  $B$. The trajectory will be a curve through the vertical plane passing through the points
  $A$ and $B$. The cost of traveling a distance $ds$ at an altitude $h$ is constant and given by
  $e^{-h/H}ds$.

  Choose a coordinate system that is well suited to this problem.
  Give an expression for the cost of the voyage between the points $A$ and $B$, and
  express the problem of minimizing this cost as a variational problem.
  Derive the associated Euler-Lagrange or Beltrami equation, as appropriate.

I am really stuck in this question. Is there anyone could solve this calculus of variation problem in terms of polar coordinate?

My attempts so far.

We should choose a polar system, to describe this situation, say, $(r_1, \theta_1)$, $(r_2, \theta_2)$ for the points $A$, $B$.
As derive an expression for cost, I guess maybe we should use integration,
diff and then make it equal to constant, then based on that, then we try to find a formula of $f$, to make

$$\frac{df}{dy} - \frac{d}{dx} (\frac{df}{dy'}) = 0?$$

For the Euler-Lagrange or Beltrami equation,  I really don't know.

HINTS:

I use Cartesian coords.Slope to x-axis = $ \tan \phi =y^{'},$ primed w.r.t. $x$

Constraint

$x$ difference is constant

$$ \int  \, dx = x_2 - x_1 = const$$

Cost or object function to minimize

$$ 1 + \int  { e^{-y/H}}{ \sqrt{1+y^{'2} }} dx = const$$

So the "Lagrangian"  is

$$   \,{ e^{-y/H}}{ \sqrt{1+y^{'2} } } $$

Now use EL equn and simplify with $ 1+H = G $

It results in an ODE with $ \phi = f( s(arc)) $ in a more simplified form for numerical solution ..

EDIT1

The ODE obtained primed on  arc basis is (if no errors)curvature of second order

$$ \phi^{'}=\frac{e^ {(y/H)}}{G \sec^2 \phi + H} $$

The aircraft path is an optimum between the advantages of reduced air resistance at high altitude and the length of travel to reach high altitude. So the answer will be somewhere between flying at ground level and going vertically up along and vertically down.
The path length is $ds=\sqrt{dx^2+dy^2}=\sqrt{1+y'^2}dx$. So the Lagrangian is $L(y,y')=\int_{-d/2}^{d/2} e^{-y/H}\sqrt{1+y'^2}dx$ with the end points fixed $y(-d/2)=y(d/2)=0$.
Euler Lagrange $\frac{\partial L}{\partial y}=\frac{d}{dx}\frac{\partial L}{\partial y'}$ gives $\frac{y''}{(1+y'^2)}=-1/H$.
This integrates to $y'=tan(c_1-x/H)$. Integrating again gives $y=H log(cos(c_1-x/H))+c_2$. Fixing up the constants to match the bc gives $y(x)=H log(\frac{cos(x/H)}{cos(d/2H)})$.


Laurent series for $\frac{e^z}{1 - z}$ for $|z| > 1$ I do this like $\dfrac{e^z}{1-z}$ = $-e \dfrac{e^{z-1}}{z-1}$ = $-e \sum_{k=0}^{\infty} \dfrac{(z-1)^k}{k!(z-1)}$ = $-e \sum_{k=0}^{\infty} \dfrac{(z-1)^{k-1}}{k!}$

However doesn't this give me the Laurent series around $|z-1| > 0$? Should I do a taylor expansion of the first term $\dfrac{-e}{z-1}$ to a geometric series to get the expansion for $|z|>1$?

Maybe I have just messed up some definitions, sorry if that's the case.

$|z|>1$ is an annulus with center $0$, thus all powers of the relevant Laurent series should be of the form $(z-0)^k$.

On the one hand $$e^z=1+z+\frac{z^2}{2}+ \dots=\sum_{k=0}^\infty \frac{z^k}{k!}$$

On the other $$\frac{1}{1-z}= -\frac{1}{z} \frac{1}{1-1/z}=-\frac{1}{z} \sum_{k=0}^\infty \frac{1}{z^k}=\sum_{k=0}^\infty- \frac{1}{z^{k+1}} $$

Try multiplying both series and collecting the terms of the same degree.

Put $1 - z = u$. So you shall get $\frac{e^z}{1 - z} = \frac{e^{1-u}}{u} = e \frac{e^{-u}}{u}$.

Now expand it in terms of $e^{-u}$ and get $e \left( \frac{1}{u} - 1 + \frac{u}{2!} - \dots \right)$

Now put the value of $U$ and finally you shall get

$$\frac{e^{z}}{1 - z} = e (\frac{1}{1-z} - 1 + \frac{1 - z}{2!} \dots )$$

The function has a pole of order $1$ at $z = 1$.


Definite integral $\int_{0}^{\infty}e^{-u}\frac{1}{\left(\sqrt{1+(h+u)^{2}}\right)^{5}}du$ Hi guys I have the following definite integral to solve:

$$\int_{0}^{\infty}e^{-u}\frac{1}{\left(\sqrt{1+(h+u)^{2}}\right)^{5}}du$$

is it possible to obtain an analytic expression? And if not why?

When I try the integration in mathematica it gives me back the integrand...

thank you in advance

Edit: $h$ is a real number so that $ 1 + (h+u)^{2}$ is always positive

Using the substitution $t=u+h$, you get
$$I=\int_0^{\infty}e^{-u}\frac{1}{\sqrt{1+(u+h)^2}^5}\,dx=e^{h}\int_h^1e^{-t}\frac{1}{\sqrt{t^2+1}^5}\,dt$$

Using the substitution $t=\tan(\theta)$, you get $dt=\sec^2(\theta)d\theta$, $t=h\rightarrow\theta=\arctan(h)=\theta_0$, $t=\infty\rightarrow\theta=\frac{\pi}{2}$:

$$\begin{array}{rcl}
I=e^{h}\int_h^1e^{-t}\frac{1}{\sqrt{t^2+1}^5}\,dt&=&e^h\int_0^{\frac{\pi}{2}}e^{\tan{\theta}}\frac{\sec^2(\theta)}{\sqrt{\tan^2(\theta)+1}^5}\,d\theta\\
&=&e^h\int_{\theta_0}^{\frac{\pi}{2}}e^{\tan{\theta}}\frac{\sec^2(\theta)}{\sqrt{\sec^2(\theta)}^5}\,d\theta\\
&=&e^h\int_{\theta_0}^{\frac{\pi}{2}}e^{\tan{\theta}}\frac{\sec^2(\theta)}{\sec^5(\theta)}\,d\theta\\
&=&e^h\int_{\theta_0}^{\frac{\pi}{2}}e^{\tan{\theta}}\frac{1}{\sec^3(\theta)}\,d\theta\\
&=&e^h\int_{\theta_0}^{\frac{\pi}{2}}e^{\tan{\theta}}\cos^3(\theta)\,d\theta\\
\end{array}$$

One posible way to continue this is $\cos^3(\theta)=\cos(\theta)\cos^2(\theta)=\cos(\theta)(1-\sin(\theta))$, so

$$\begin{array}{rcl}
I&=&\underbrace{e^h\int_{\theta_0}^{\frac{\pi}{2}}e^{\tan(\theta)}\cos(\theta)\,d\theta}_{I_1}+\underbrace{e^h\int_{\theta_0}^{\frac{\pi}{2}}e^{\tan(\theta)}\sin^2(\theta)\cos(\theta)\,d\theta}_{I_2}
\end{array}$$

For $I_1$, you could do it by parts (haven't done it myself yet)
For $I_2$, you could do it by parts, plainly or trying to use first the substitution $x=\sin(\theta)$, so $dx=\cos(\theta)d\theta$ and $\tan(\theta)=\frac{x}{\sqrt{1-x^2}}$ (haven't tried it either).

Good luck!


What's the difference between predicate and propositional logic? I'd heard of propositional logic for years, but until I came across this question, I'd never heard of predicate logic.  Moreover, the fact that Introduction to Logic: Predicate Logic and Introduction to Logic: Propositional Logic (both by Howard Pospesel) are distinct books leads me to believe there are significant differences between the two fields.  What distinguishes predicate logic from propositional logic?

Propositional logic (also called sentential logic) is logic that includes sentence letters (A,B,C) and logical connectives, but not quantifiers. The semantics of propositional logic uses truth assignments to the letters to determine whether a compound propositional sentence is true.

Predicate logic is usually used as a synonym for first-order logic, but sometimes it is used to refer to other logics that have similar syntax. Syntactically, first-order logic has the same connectives as propositional logic, but it also has variables for individual objects, quantifiers, symbols for functions, and symbols for relations. The semantics include a domain of discourse for the variables and quantifiers to range over, along with interpretations of the relation and function symbols.

Many undergrad logic books will present both propositional and predicate logic, so if you find one it will have much more info. A couple of well-regarded options that focus directly on this sort of thing are Mendelson's book or Enderton's book.

This set of lecture notes by Stephen Simpson is free online and has a nice introduction to the area.

I think propositional logic consists of sentences names by sentence letters e.g $(P, Q, R, S)$ with logical connectives for compounds statements, it uses truth assignments to letters to whether it is true or false, with no quantifiers.

While predicate contains symbols, function, objects, relation and quantifiers.


Prove that if $ u(x,t) = f(x-ct) + g(x + ct)$ then $u_{tt} = c^2 u_{xx}$ Prove that if $$ u(x,t) = f(x-ct) + g(x + ct)$$ then $$u_{tt} = c^2 u_{xx}$$

My approach:
Let $f(x-ct) = f(A)$ and $g(x+ct)=g(B)$

$$ u_t = \frac{\partial u}{\partial t} = \frac{\partial f}{\partial A }\frac{\partial A}{\partial t } + \frac{\partial f }{\partial B } \frac{\partial B }{\partial t } $$

$$ u_{tt} = \frac{\partial }{\partial t} \left(  \frac{\partial u}{\partial t }  \right) = \frac{\partial^2 f }{\partial t \partial A } \cdot \frac{\partial    A}{\partial t } + \frac{\partial f }{\partial A }  \cdot \frac{\partial^2 A }{\partial t^2 }   +  \frac{\partial^2 f}{\partial t \partial B } \cdot \frac{\partial B }{\partial t} + \frac{\partial f }{\partial B } \cdot \frac{\partial^2 B }{\partial B \partial t } $$

Evaluating some partials
$$\frac{\partial A }{\partial t } = -c ,  \frac{\partial^2 A }{\partial t^2} =0, \frac{\partial B }{\partial t } =c , \frac{\partial^2 B }{\partial t^2 } =0$$
hence
$$u_{tt} =\frac{\partial^2 f }{\partial t \partial A } \cdot -c + \frac{\partial^2 f }{\partial t \partial B }\cdot c$$

Using similar approach,
$$ u_{xx} =\frac{\partial^2 f }{\partial x \partial A } + \frac{\partial^2 f }{\partial x \partial B }$$

Is what I did correct? I am stuck at this level. What needs to be done to complete the proof?

As @Mattos and @Did have suggested we will use the following conventions:

$$f(x-ct)=f(A(x,t))\qquad A(x,t)=x-ct$$
$$g(x+ct)=g(B(x,t))\qquad B(x,t)=x+ct$$

Let us first evaluate the partial derivatives of $A$ and $B$:

$$\frac{\partial A}{\partial x} = 1\qquad \frac{\partial A}{\partial t}=-c\qquad
\frac{\partial B}{\partial x} = 1\qquad \frac{\partial B}{\partial t} = c$$

Then we proceed to evaluate $u_{xx}$ and $u_{tt}$, first for $x$:
$$u(x,t)=f(A(x,t))+g(B(x,t))$$ hence
$$
\frac{\partial u}{\partial x} = f'(A(x,t)) \frac{\partial  A}{\partial x}+ g'(B(x,t))\frac{\partial  B}{\partial x}= f'(A(x,t))+g'(B(x,t))$$
and
$$
\frac{\partial^2u}{\partial x^2} = \frac{\partial}{\partial x}(f'(A(x,t))+g'(B(x,t)))=f''(A(x,t))\frac{\partial A}{\partial x }+g''(B(x,t))\frac{\partial B}{\partial x}$$ that is,
$$\frac{\partial^2u}{\partial x^2} = f''(A(x,t))+g''(B(x,t))$$

Likewise, with respect to $t$:
$$
\frac{\partial u}{\partial t} = f'(A(x,t)) \frac{\partial  A}{\partial t}+ g'(B(x,t))\frac{\partial  B}{\partial t}= -cf'(A(x,t))+cg'(B(x,t))$$
and $$
\frac{\partial^2u}{\partial t^2} = \frac{\partial}{\partial t}(-cf'(A(x,t))+cg'(B(x,t)))=-cf''(A(x,t))\frac{\partial A}{\partial t }+cg''(B(x,t))\frac{\partial B}{\partial c}$$ that is, $$
\frac{\partial^2u}{\partial t^2}= c^2f''(A(x,t))+c^2g''(B(x,t))$$

Now we can show the desired equality:

$$\frac{\partial^2u}{\partial t^2}=c^2f''(A(x,t))+c^2g''(B(x,t))=c^2(f''(A(x,t))+g''(B(x,t)))=c^2\frac{\partial^2 u}{\partial x^2}$$
therefore,
$$u_{tt}=c^2u_{xx}$$

as required.

$$ \frac{\partial}{\partial t}\left( f'(A(x,t))\frac{\partial A}{\partial t} \right) = \left( f''(A(x,t))\frac{\partial A}{\partial t} \right )\frac{\partial A}{\partial t} + f'(A(x,t))\left( \frac{\partial^2 A}{\partial t^2}  \right) $$ i.e. $$ \frac{\partial}{\partial t}\left( f(A(x,t))\frac{\partial A}{\partial t} \right) = f''(A(x,t))\left(\frac{\partial A}{\partial t}\right)^2 +f'(A(x,t)) \left( \frac{\partial^2 A}{\partial t^2}  \right)$$ So given that $\frac{\partial^2 A}{\partial t^2}  = 0 $ you have $$ \frac{\partial}{\partial t}\left( f(A(x,t))\frac{\partial A}{\partial t} \right) = f''(A(x,t))\left(\frac{\partial A}{\partial t}\right)^2 $$


The "magic diagram" is cartesian I am trying to solve an exercise from Vakil's lecture notes on algebraic geometry, namely, I want to show that
$\require{AMScd}$
\begin{CD}
    X_1\times_Y X_2 @>>> X_1\times_Z X_2\\
    @V V V @VV V\\
    Y @>>> Y \times_Z Y
\end{CD}

is a cartesian diagram. I think I've figured out where the maps come from: The lower map is the diagonal induced from the universal property of $Y \times_Z Y$, the upper map is coming from the universal property of $X_1\times_Z X_2$ (this is one of the previous exercises in Vakil's notes), the map on the right also comes from the universal property of $Y \times_Z Y$ since we have two maps from $X_1\times_Z X_2$ to $Y$ whose composition with $Y\rightarrow Z$ coincides, and finally the map on the left side is either composition $X_1\times_Y X_2 \rightarrow X_i \rightarrow Y$. At this point, I don't even see why this diagram should be commutative.

But even discarding the issue of commutativity, given some $T$ instead of $X_1\times_Y X_2$ making the above diagram commute, I have no clue how to obtain a canonical map $T \rightarrow X_1\times_Y X_2$.

I could solve all the other problems in this section of his notes, but this one eludes me. Any help or solution (preferably just using the universal properties that we're given) would be greatly appreciated.

First, why is the diagram commutative: you've got the following commutative diagram:

It is commutative precisely because this is how we defined the map $X_1 \times_Y X_2 \to X_1 \times_Z X_2$. The bottom right square is used to define $Y \to Y \times_Z Y$.

Now, you diagram is commutative iff the two maps $X_1 \times_Y X_2 \to Y \times_Z Y$ are equal, iff each component maps are equal.

The red path is used to define the (first component of the) map that factors through $X_1 \times_Y X_2 \to X_1 \times_Z X_2 \to Y \times_Z Y$
The blue path is used to define the (first component of the) map that factors through $X_1 \times_Y X_2 \to Y \to Y \times_Z Y$.

As you can see, they are equal. Therefore the magic diagram commutes.

Now, the universal property. Suppose you're given $T \to X_1 \times_Z X_2$ and $T \to Y$  such that the two maps $T \to Y \times_Z Y$ are equal. In other words, you're given maps $T \to X_1$, $T \to X_2$ and $T \to Y$, such that the two maps $T \to X_i \to Z$ are equal, and the maps the blue path and the red path are equal (where $T$ is in the position of $X_1 \times_Y X_2$). As you can see, this is precisely the same thing as giving two maps $T \to X_i$ such that $T \to X_i \to Y$ are equal, because then the fact that the maps into $Z$ are equal is a consequence of the fact that the maps into $Y$ are equal. So there's a unique map $T \to X_1 \times_Y X_2$ making everything commute.

Considering that Vakil introduces the Yoneda lemma after this exercise, I didn't dare give the proof using it. But by the Yoneda lemma, you can just consider the case of sets; in the equations that you'll write, you'll arrive at the same conclusion -- that giving a maps that make everything commute will give you a redundant condition that the images in $Z$ are the same, and that the fibered product of the whole thing is the fibered product over $Y$.

Vakil's algebraic geometry notes on "schemes" gives this as an exercise (see exercise 1.3.s on page 37 in the attached link). Any scheme has an open cover of affine schemes and let us first prove it for affine schemes.
https://math.stanford.edu/~vakil/216blog/FOAGnov1817public.pdf
Let $A\rightarrow B$ be a map of commutative unital rings and let $C_1,C_2$ be commutative unital $B$-algebras. Let $m:B\otimes_A B \rightarrow B$ be the multiplication map and let $I:=ker(m)$. We want an explicit isomorphism
$$B\otimes_{B\otimes_A B}(C_1\otimes_A C_2) \cong C_1\otimes_B C_2.$$
Note that there is a canonical isomorphism
$$ B\otimes_{B\otimes_A B}(C_1\otimes_A C_2)\cong C_1\otimes_A C_2/I(C_1\otimes_A C_2)$$
where we view $C_1\otimes_A C_2$ as a left $B\otimes_A B$-module via the canonical map.  The canonical map
$$C_1\otimes_A C_2 \rightarrow C_1\otimes_B C_2$$
induce a canonical map
$$F': B\otimes_{B\otimes_A B}(C_1\otimes_A C_2) \cong C_1\otimes_A C_2/I(C_1\otimes_A C_2)   \rightarrow C_1\otimes_B C_2.$$
We want a map in the other direction: There is a canonical map
$$F: C_1\times C_2 \rightarrow C_1\otimes_A C_2/I(C_1\otimes_A C_2)$$
defined by
$$F(x,y):=\overline{x\otimes y}.$$
The map $f$ induce a map of rings $F$
$$F: C_1\otimes_B C_2 \rightarrow C_1\otimes_A C_2/I(C_1\otimes_A C_2).$$
Question: "I am trying to solve an exercise from Vakil's lecture notes on algebraic geometry, namely, I want to show that
$\require{AMScd}$
\begin{CD}
    X_1\times_Y X_2 @>>> X_1\times_Z X_2\\
    @V V V @VV V\\
    Y @>>> Y \times_Z Y
\end{CD}
is a cartesian diagram."
Answer: It seems to me that $F \circ F'=F' \circ F=Id$ is the identity. Hence there is a canonical isomorphism of commutative unital rings
$$B\otimes_{B\otimes_A B}(C_1\otimes_A C_2) \cong C_1\otimes_B C_2.$$
If we let $Y:=Spec(B), Z:=Spec(A), X_i:=Spec(C_i)$ we get a canonical isomorphism
$$Y\times_{Y\times_Z Y}(X_1\times_Z X_2)\cong X_1\times_Y X_2.$$
All maps are "canonical" and using a glueing lemma the theorem should follow.
Note: Some of the above proofs are overly complicated and you speak of algebraic geometry and Vakil's notes on algebraic geometry and schemes - the above proof is completely elementary.