Probability that $n$ random walks (1D) intersect a single point I am struggling finding a relation to determine the probability $n$ random walks (1D) intersect in a single point at step $s$. In the method below my attempts. My method is somewhat intuitive based. I am looking for more rigorous proof.
note:
This question arises from someone who claims that a matching cumulative digit sum of: $\pi$, $e$ and $\varphi$ (golden ratio) is unique and "cosmological" [1]. I tend to disprove it. This digit sum can be seen as a random walk if the constants are normal (every digit occurs with same frequency).
Method:
For every step $s$ on the random walk we can determine the probability density function if we know the standard deviation on every step $s$.
The standard deviation of a single step can be calculated it's a discrete uniform distribution "equally likely outcomes", where $q$ is the number of outcomes e.g. the number of digits $[0,1,2,3,4,5,6,7,8,9]$, $q=10$:
$$\sigma=\sqrt{\frac{q^{2}-1}{12}} $$
All the (1D) random walks start in the origin for this example. The standard deviation will grow with every step $s$, the variance is proportional to the number of steps [2].
$$Var(s)=s \cdot \sigma^{2}$$
$$\sigma(s)=\sqrt{s} \cdot \sigma$$
While the bins grow rapid I assume a normal approximation of the Binomial distribution.
$$f(x)=\int_{-\infty}^{\infty} {\frac {1}{\sigma {\sqrt {2\pi }}}}e^{-{\frac {1}{2}}\left({\frac {x}{\sigma }}\right)^{2}}dx $$
The probability that $n$ random walks intercept in a single point is (not sure):
$$p(s)=\int_{-\infty}^{\infty} \left[ {\frac {1}{\sigma {\sqrt {2\pi }}}}e^{-{\frac {1}{2}}\left({\frac {x}{\sigma }}\right)^{2}} \right]^n dx $$
With help of Wolfram Alpha [3] the solution is found for $n=3$ meaning the probability of $3$ point intersecting random walks.
$$p(s)=\frac{1}{2 \sqrt{3} \ \pi \ \sigma^{2}} \cdot \frac{1}{s}$$
The total probability $p(n)$ is proportional to the reciprocal sum of $s$. So the total probability is proportional to the harmonic series:
$$p(n)=\frac{1}{2 \sqrt{3} \ \pi \ \sigma^{2}} \cdot \sum_{s=1}^{\infty}\frac{1}{s}$$
This series diverges, meaning there are infinate point intersections of $n=3$ random walks. So a matching cumulative digit sum of $\pi$, $e$ and $\varphi$ is not unique, probability $\sim 8 \%$ for the first 1200 digits (see graph).
Question
Does anyone know the general formula for the probability $p(n)$ that $n$ random walks (1D) intersect a single point?

import numpy as np

#Elements of digits [0,1,2,3,4,5,6,7,8,9] rescaled to fit random walk
array=[-9,-7,-5,-3,-1,1,3,5,7,9]

#steps, in single random walk, x walks to intercept, number of trial to find intercept
steps=2500
xwalks=3
trials=1500

#Set output array to zero
count=np.full([steps],0)

for n in range(trials):

    #Identify initial array, set total array to zero
    w0=np.random.choice(array,steps)
    w0=np.cumsum(w0)
    total=np.full([steps],0)

    #Select x random walk check for intercept
    for m in range(xwalks-1):

        #Next current random walk
        w=np.random.choice(array,steps)
        w=np.cumsum(w)

        #Compare previous and current random walk
        eq=np.equal(w0,w)
        eq=eq.astype(int)

        #Count intercepts
        total=total+eq

        #Set current walk to previous
        w0=w

    #Sum all interceptions for all trials
    count=count+np.where(total==(xwalks-1),1,0)

#Print output
print(count)
print(np.sum(count))
print(np.sum(count)/trials)

The probability $n$ random walks starting in origin (1D) intersect a single point can be calculated with:
$$p(s)=\int_{-\infty}^{\infty} \left[ {\frac {1}{\sigma {\sqrt {2\pi }}}}e^{-{\frac {1}{2}}\left({\frac {x}{\sigma }}\right)^{2}} \right]^n dx$$
Solutions have been found with Wolfram Alpha 1. This solution can be written as a function of the number of steps $s$. So the probability $p$ at $s$ steps can be calculated with a empirical found formula:
$$p(s)= \frac{1}{g(n) \cdot  \sigma ^{(n-1)}  } \cdot s^{-\frac{1}{2}(n-1)} $$
Where the function for $g(n)$ is found as:
$$g(n)=\sqrt { n} \cdot (2 \pi)^{\frac{1}{2}(n-1)}$$
The total probability over all steps $s$ is only dependent upon the $p$-series formed by $s$. This summation can be calculated with the Riemann zeta function:
$$\zeta(\small{\frac{1}{2}(n-1)} \normalsize) =\sum\limits_{s=1}^{\infty}s^{- \frac{1}{2}(n-1)}$$
$$p(n)=\frac{1}{g(n) \cdot \sigma^{(n-1)}} \cdot \sum\limits_{s=1}^{\infty}s^{- \frac{1}{2}(n-1)} $$
Graph information
Below a table and a plot for the probabilities of $p(n)$ point coinciding random walks (1D). Details:

The standard deviation is chosen: $10$ equal likely outcomes per step:
$$\sigma=\sqrt{\frac{99}{12}}$$
For infinate random walks $n\rightarrow \infty$ the $p$-series converges to $1$. This probability is plotted as: $p_{\infty}(n)$.
$p(n)$ can be graphed as an continuous function.
Values $n<3$ have not been graphed while Riemann zeta $\zeta(<1)$ are resulting in negative probabilities.

Observations:

$n=3$ random walks have infinate single point intersections. $p$-series: $\sum\limits_{s=1}^{\infty}s^{-1}=\infty$, Riemann zeta: $\zeta(1)=\infty$ both have infinity probability $p(n)\rightarrow \infty$.
$n=2$ random walks have infinate single point intersections for $p$-series: $\sum\limits_{s=1}^{\infty} s^{-\frac{1}{2}}=\infty$ , interpretation Riemann zeta is unclear: $\zeta(\frac{1}{2})=-1.46035...$ resulting in a negative probability $p(2)$.
It is possible that $n\geq4$ random walks never point intersect. For $n=4$ only $\sim 0.35 \%$ of them will point intersect (with 10 equal likely outcomes per step).
The probability $p(n)$ plot of $n$ random walks (1D) intersecting a single point is directly related to the $p$-series. A relation with Riemann zeta is unclear while the number of walks $n=a+ib$ would be a complex number.
I learned this has to do with: recurrence and transience 2.

Any more rigorous proofs or information is welcome please.

I now realise that your rebuttal of my analysis in your comment above at Probability that $n$ random walks (1D) intersect a single point was in fact valid, as I had made a mistake in my analysis. I assumed incorrectly that I could simply add together the probabilities of collision after one step, two steps etc. to get the total probability of collision. However, these events are not mutually exclusive, since random walks can collide at multiple steps, so if the probability of collision at step 1 was 0.6 and the probability of collision at step 2 was 0.5, I would already have a probability exceeding 1. Hence, the correct process is to work out the probability of non-collision before step m multiplied by the probability of collision at step m, and only then add together the probabilities. Alternatively, I could just calculate the probability of non-collision at or before step m by multiplying together probabilities, then subtract it from one, and take the limit as m tends to infinity.

Edit:
This method describes collision random walk with probability per step is: [-1,1] 50%.
s: step number in random walk, n: number of intersecting random walks.
Probability intersecting at single step position:
$$p(s)= \sum_{k=0}^{s} \left(\frac{1}{2^{s}}  \binom{s}{k}\right)^{n}$$
Total probability over all steps:
$$p(n)=\sum_{s=1}^{\infty}\sum_{k=0}^{s} \left(\frac{1}{2^{s}}   \binom{s}{k} \right)^{n}$$

I have now created a spreadsheet to calculate the answer to your question, which is:

n
p(n)

1
1

2
1

3
0.907472937

4
0.382922701

5
0.147129979

6
0.062758395

7
0.028516044

8
0.013419184

9
0.006446336

10
0.003136593

11
0.001538874

12
0.000759198

I am not sure how accurate my results are, but if you need better accuracy, you could extend the spreadsheet tables as required.
My spreadsheet uses data tables, and it appears that Excel cannot handle nested data tables, so the table above was produced by manually typing in the first twelve input values for n and copying the result. For a larger data set, a quick script could be written to automate the process.
The spreadsheet is available at https://groups.io/g/UnsolvedProblems/message/12251.
I can now see that your question is related to Pólya's Random Walk constants, but because you are essentially asking a different question, I don't think the answer to your question should directly equate to Pólya's Random Walk constants.
In terms of the normal approximation you mentioned in your analysis, the conditions of the Central Limit Theorem state under which circumstances a normal approximation applies, which can be found at https://en.wikipedia.org/wiki/Central_limit_theorem.


How prove this inequality $\sum\limits_{cyc}\frac{1}{a+3}-\sum\limits_{cyc}\frac{1}{a+b+c+1}\ge 0$ show that:
$$\dfrac{1}{a+3}+\dfrac{1}{b+3}+\dfrac{1}{c+3}+\dfrac{1}{d+3}-\left(\dfrac{1}{a+b+c+1}+\dfrac{1}{b+c+d+1}+\dfrac{1}{c+d+a+1}+\dfrac{1}{d+a+b+1}\right)\ge 0$$
where $abcd=1,a,b,c,d>0$

I have show three  variable inequality

Let $ a$, $ b$, $ c$ be positive real numbers such that $ abc=1$.
Prove that
$$\frac{1}{1+b+c}+\frac{1}{1+c+a}+\frac{1}{1+a+b}\leq\frac{1}{2+a}+\frac{1}{2+b}+\frac{1}{2+c}$$
also see:can  see
：http://www.artofproblemsolving.com/Forum/viewtopic.php?f=51&t=243

from  this equality,I have see a nice methods:

I think this Four varible  inequality is also true

First,Thank you Aditya answer,But I read it your solution,it's not true

We have
$$\begin{align}
\frac3{a+b+c+1} &- \frac1{a+3} - \frac1{b+3} - \frac1{c+3}\\
&= \sum_{cyc}^{a, b, c} \left(\frac1{a+b+c+1}-\frac1{a+3} \right) \\
&= \frac1{a+b+c+1} \sum_{cyc}^{a, b, c}\frac{2-b-c}{a+3} \\
&= \frac1{(a+b+c+1)\prod_{cyc}^{a, b, c}(a+3)} \sum_{cyc}^{a, b, c} (18-6a-4ab-a^2b-ab^2-6a^2) \\
&\le \frac1{1\times3^3} \sum_{cyc}^{a, b, c} (18-6a-4ab-a^2b-ab^2-6a^2)
\end{align}$$

using $a, b, c > 0$. Summing over four such inequalities, we get
$$3\sum_{cyc}\frac1{a+b+c+1} - 3\sum_{cyc} \frac1{a+3} \\ \le \frac2{27}\left( 108-\sum_{cyc}\left(9(a+a^2)+4(2ab+bd)+(a^2b+ab^2+a^2c+ac^2+b^2d+bd^2)\right) \right)$$

Now by AM-GM and the constraint, we have that  $\sum_{cyc} a^mb^n \ge 4\sqrt[4]{(abcd)^{m+n}}=4$ for all $m, n \ge 0$, so RHS $\le 0$ and we are done.

P.S. the method looks general, though I wouldn't want to write down the cyclic sums for more variables!

Partial Proof:
For general case of n variables, the inequality converts to:

  $$\sum_i^n \frac1{1+a_1+a_2+\cdots+a_n-a_i}\le \sum_i^n\frac1{n-1+a_i}$$

Similiar to the given proof we can convert $\frac {a_1}{a_1+(n-1)}$ like this:
$$\frac{a_1}{a_1+(n-1)}=\frac{a_1}{a_1+(n-1)(a_1a_2\cdots a_n)^{1/n}}$$
Dividing numerator and denominator by $a_1^{1/n}$:
$$=\frac{a_1^{(n-1)/n}}{a_1^{(n-1)/n}+(n-1)\left(\frac{a_1a_2\cdots a_n}{a_1}\right)^{1/n}}
$$
Finally using AM-GM gives:
$$\frac{a_2+a_3+\cdots+a_n}{(n-1)}\ge\left(a_2a_3\cdots a_n\right)^{1/(n-1)}$$
Or:
$$(n-1)\left(a_2a_3\cdots a_n\right)\le (a_2+a_3+\cdots+a_n)^{n-1}$$
$$=\frac{a_1^{(n-1)/n}}{a_1^{(n-1)/n}+(n-1)\left(\frac{a_1a_2\cdots a_n}{a_1}\right)^{1/n}}
\ge\frac{a_1^{(n-1)/n}}{a_1^{(n-1)/n}+a_2^{(n-1)/n}+\cdots+a_n^{(n-1)/n}}$$

So, $$\sum_i^n\frac{a_i}{a_i+(n-1)}\ge\sum_i^n\frac{a_1^{(n-1)/n}}{a_1^{(n-1)/n}+a_2^{(n-1)/n}+\cdots+a_n^{(n-1)/n}}=1\tag{i}$$
We have proved what we need for the general case of n-variables, try putting $n=3$.

Since product of all numbers is 1, we can define new fractions as: Let $$\displaystyle a_1:=\frac{x_1}{x_2},a_2:=\frac{x_2}{x_3},\cdots,a_n:=\frac{x_n}{x_1}$$

Notice that in the given proof:
$$\frac{b}{ab+b+1}=\frac{x_2/x_3}{x_1/x_2.x_2/x_3+x_2/x_3+1}=\frac{x_2}{x_1+x_2+x_3 }$$

Now similiar to the given proof we can show that(step unproven):
$$\frac{2}{a_1+(n-1)}-\frac{1}{1+a_2+a_3+\cdots+a_n}-\frac{x_2}{x_!+x_2+\cdots+x_n }\ge0$$
$$\frac{2}{a_1+(n-1)}\ge \frac{1}{1+a_2+a_3+\cdots+a_n}+\frac{x_2}{x_1+x_2+\cdots+x_n }$$

$$\frac1{a_1+(n-1)}+\frac1{a_1+(n-1)}\ge\frac{1}{1+a_2+a_3+\cdots+a_n}+\frac{x_2}{x_1+x_2+\cdots+x_n }$$
Since $\displaystyle \sum_i^n\frac{x_2}{x_1+x_2+\cdots+x_n }=1$
$$\frac1{a_1+(n-1)}+\frac1{a_1+(n-1)}\ge\frac{1}{1+a_2+a_3+\cdots+a_n}+1$$
$$\sum_{cyc}\frac{1}{a_1+(n-1)}-\sum_{cyc,i}\frac1{1+a_2+a_3+\cdots+a_n }\ge1-\sum_{cyc}\frac{1}{a_1+(n-1)}\ge0 $$
The$\ge0$ part, we have proved in (i).
So,
$${\large \sum_{cyc}\frac{1}{a_1+(n-1)}\ge\sum_{cyc,i}\frac1{1+\sum_{cyc,j\ne i}a_j}}\Box$$


Where can one post proofs of unsolved maths problems? With certifucates etc. There is a 0.1% chance I have solved an unimportant yet unsolved maths problems.  I live in the UK - can get to London. Where can I get certificate etc if I do solve it. I'm going to talk to my maths teacher (PHD). And If on the extremely rare chance I solve it where do I go?

When you are acquainted enough with mathematics, you should be able to write a clean proof. Learn LaTeX, write your proof in LaTeX, publish it on Arxiv. On this way, you don't have to go by some mathematics professor who may be in dire need of an important publication and it costs no money. If however Arxiv doesn't accept your proof it will be because it is either because your proof is obviously not based on real mathematics or obviously wrong (or you are unable to use LaTeX properly). If Arxiv accepts, soon you will see a thread here or on math overflow on your approach if the problem is really important and your approach seems reasonable enough.

Of course, this isn't THE way to go, just the way I would do it. Technically I think, as Mathmo123 mentioned, this question would be better handled in Academia.


$\mathbb{R}$ with the finite complement topology Let $X=\mathbb{R}$ be given with the collection $\tau$ where
$$
\tau = \{U\subset X: |X\setminus U|<\aleph_0\}\cup \{\emptyset\}
$$
I was sitting at my computer, when I suddenly asked myself:
"How is $\tau$ actually a topology on $\mathbb{R}$?". It is supposed to satisfy the arbitrary union condition, but it doesn't. Indeed
$$
\bigcup_{i\in \mathbb{N}} \mathbb{R}\setminus \{i\} \notin \tau
$$
but each of $\mathbb{R}\setminus \{i\} \in \tau$.
Can someone explain to me how $\tau$ is a topology?

edit
as Thomas Andrews points out, I was confusing unions with intersections and, in general, just being an idiot.

To get a topology you need to include $\emptyset$ in $\tau$. With that fixed the proof is easy.

$\tau$ is closed under intersection of two sets (and hence finitely many). If $A$ and $B$ are both in $\tau$ and neither is empty, then there are only finitely many elements missing from $A$ and finitely many missing from $B$. For an element $x$ to not be in $A\cap B$ we must have either $x\notin A$ or $x\notin B$, which can happen only for finitely many $x$. Of course, if one of $A,B$ is empty, so is the intersection so $A\cap B$ is still in $\tau$
Closure under unions is even easier. If $U_i$ are elements of $\tau$ for some indices $i\in I$, then if at least one of the sets, say $U_{i_1}$, is non-empty then there are only finitely many elements of $X$ missing from $U_{i_1}$. For an element $x\in X$ to not be in $\bigcup_{i\in I}U_i$ we must have $x\notin U_{i_1}$, so this can only happen for finitely many $x\in X$. Again, if all the $U_i$:s are empty their union is still in $\tau$.

The union you have written is all of $\mathbb{R}$ which is in the topology.


Amount of elements in finite vector space. I'm trying to resolve two exercises from Kostrikin's book.
Ex. 1

How many elements contains vector space $\mathbb{F}_p^n$ (vectors
$(x_1,x_2,\dots,x_n)$ of length $n$) over a field $\mathbb{F}_p$ with $p$
elements? How many solutions has equation
$a_1x_1+a_2x_2+\dots+a_nx_n=0$ (not all $a_i=0$)?

Ex. 2

How many $k$-dimmension subspaces ($1\le k\le n$) contains
$n$-dimension vector space $V$ over a field $F_q$ with $q$ elements.

I think, I resolve first exercise:
$$\left|\mathbb{F}_p^n\right|=p^n$$
because I need to create vector of length $n$. I can choose first element on $p$ ways, second too.... so $p\cdot p\cdot p\cdots p$. Number of solutions is an amount of linear dependent vectors in this space. Dimension of this space is equal $n$, so a maximum set of independent vectors contains $n$ vectors. Number of solution is equal $p^n-n$?
In case of second exercise I have two solutions.
First:
There is only one $k$-dimension subspace? Because all spaces with dimension $k$ are isomorphic.
Second:
Base of $V$ space contains $n$ vectors. So I can choose ${n \choose k}$ vectors from $V$ base and create $k$-dimension subspace. So there is ${n \choose k}$ subspaces.
Are any of my solutions correct?
Thanks.

Your answer to the first exercise is correct.

For the second exercise, first note that they ask for the number of $k$-dimensional subspaces, not the number of isomorphism classes of $k$-dimensional subspaces. If they were asking for isomorphism classes, then yes you're right there would only be 1. Also, you make the incorrect assumption that every $k$-dim subspace can be obtained as the span of a subset of your basis. This is not true. For example, in $F^2$ (let $F := \mathbb{F}_p$), you can take the basis $\{(1,0),(0,1)\}$, but here subsets of the basis yield only two distinct 1-dim subspaces, even though there are many more. For example, what about the subspace generated by $(1,1)$? In this example, $F^2$ should be thought of as a plane, and 1-dim subspaces are just lines in the plane going through the origin, which are classified by their slope (which may be infinity for the vertical line).

To correctly count the number of $k$-dim subspaces, note that any such subspace has a basis of $k$ vectors, and thus we can begin by counting the number of sets of $k$ linearly independent vectors in $V$, which we will identify with $F^n$. For the first vector you have $p^n-1$ choices (anything but $0$). For the second, you have $p^n-p$ choices (anything but a vector in the span of the first), and so on. Thus, you have
$$\prod_{j=0}^{k-1}(p^n-p^j)$$
possible ordered sets of $k$ linearly independent vectors in $V$. Thus we have a map (of sets):
$$f : \{\text{ordered lists of $k$ linearly independent vectors in $V$}\}\longrightarrow \{\text{$k$-dim subspaces of $V$}\}$$
(where $f(v_1,\ldots,v_k) = \text{Span}\{v_1,\ldots,v_k\}$) which is surjective, but not injective. We would like to count the size of $f^{-1}(U)$, where $U\le V$ is a $k$-dim subspace. Since $f^{-1}(U)$ is just the set of ordered bases of $U$, we find that
$$|f^{-1}(U)| = \text{the number of ordered bases of $U$}$$
Identifying $U$ with $F^k$, we find that the number of ordered bases of $U$ are in bijection with matrices in $GL_k(F)$ (this group acts freely and transitively on the set of such ordered bases, or alternatively, any such ordered basis gives you a matrix in $GL_k(F)$ with elements of the basis as columns). Thus, $|f^{-1}(U)| = |GL_k(F)|$. Since this doesn't depend on $U$, we find that the number of $k$-dim subspaces of $V$ is precisely:
$$\frac{\prod_{j=0}^{k-1}(p^n-p^j)}{|GL_k(F)|}$$
By the same reasoning as above, the size of $GL_k(F)$ is
$$|GL_k(F)| = \prod_{j=0}^{k-1}(p^k-p^j)$$
so:
$$\frac{\prod_{j=0}^{k-1}(p^n-p^j)}{|GL_k(F)|} = \frac{\prod_{j=0}^{k-1}(p^n-p^j)}{\prod_{j=0}^{k-1}(p^k-p^j)} = \prod_{j=0}^{k-1}\frac{p^{n-j}-1}{p^{k-j}-1}$$

After 4 years I faced this exercise again and I found that first exercise is not solved properly. First part is ok and $\left|\mathbb{F}_p^n\right|=p^n$. Second part is wrong. Number of solutions is not equal $p^n-n$.

My new solution:

Let's begin on count how many solution has this equation:
$$
a_1x_1+a_2x_2=0\;\;\;\;\;\; a_i,x_i\in\mathbb{F}_p
$$
Let's assume that $a_1\not =0$ (For $a_2$ result will be the same). Let's assign any value for $x_2$ (we have $p$ possibilities). Then $a_2x_2'=r$ ($x_2'$ is assigned value). $\mathbb{F}_p$ is a field, so $r$ has additive inverse element $-r$.
$$a_1x_1=-r$$
Basing on the same reason (and $a_1\not=0)$ $a_1$ has multiplicative inverse element $a_1^{-1}$, so we have solution.
$$
x_1=-ra_1^{-1}$$
We have $p$ solutions for this equation.

Let's start with general solution right now.
$$
a_1x_1+a_2x_2+a_3x_3+\cdots+a_nx_n=0$$
Let's assume that $a_1\not =0$ (We could did it for any $a_i$) and let's assign any values for $x_2,x_3,x_4,\cdots x_n$ (We have $p^{n-1}$ possibilities). Then let's evaluate this expression. Result:
$$
a_1x_1+k=0\;\;\;\;\;\;k=a_2x_2'+a_3x_3'+\cdots+a_nx_n'
$$
Where $x_i'$ is assigned value. This equation has only one solution, so general equation has $p^{n-1}$ solutions, not $p^n-n$.

Is there any other way to find this value? On is my solution OK?

Thanks

Thanks @ancientmathematician I tried with rank-nullity theorem. Here is my result:

$A$ is linear transformation $A:\mathbb{F}_p^n\rightarrow\mathbb{F}_p$.
$$
A(x)=\sum_{i=1}^na_ix_i
$$
Domain of $A$ is whole $\mathbb{F}_p^n$, so
$$
\mathrm{dom}{A}=\mathbb{F}_p^n\;\Rightarrow\; \mathrm{dim}\,\mathrm{dom}{A}=n
$$
Image of $A$ is whole $\mathbb{F}_p$, so
$$
\mathrm{im}{A}=\mathbb{F}_p\;\Rightarrow\; \mathrm{dim}\,\mathrm{im}{A}=1
$$
From rank-nullity theorem
$$
\mathrm{dim}\,\mathrm{dom}{A}=\mathrm{dim}\,\mathrm{ker}{A}+\mathrm{dim}\,\mathrm{im}{A}
$$
i can figure out value of kernel dimension
$$
n=\mathrm{dim}\,\mathrm{ker}{A}+1\Rightarrow\mathrm{dim}\,\mathrm{ker}{A}=n-1
$$
Kernel of transformation is set of vectors which value is 0. So i understand i'm looking for $|\mathrm{ker}{A}|$. I'm not sure how to find amount of elements in kernel. Here is my try:

I know dimension of kernel and I know that kernel is linear space, so base of this set has $n-1$ elements. I can take any base so i'll take 'default'
$$
(1,0,0,\cdots,0)\;(0,1,0,\cdots,0)\;(0,0,1,\cdots,0)\cdots(0,0,0,\cdots,1)
$$
All vectors has $n-1$ coordinates. I can generate $p^{n-1}$ vectors basing on this set, so equation from begging of exercise has $p^{n-1}$ solutions.

Is that correct?


Magma function for modulo irreducible polynomial So, I am trying to make a program in Magma which returns the value table of a given function F over a field $GF(2^n)$. To do so I need a irreducible polyomial. For example, I've considered $GF(2^3)$ and the irreducible polynomial $p(x)=x^3+x+1$.

My program started like this:

F<a>:=GF(2^3);
for i in F do
i mod a^3+a+1;
end for;

The 'mod' apperantly only works with integers, is there a polynomial version for this?

The mod function works for polynomials, provided they are recognized by Magma as being elements in a polynomial ring. For example, put F := GF(2); and P<a> := PolynomialRing(F); and you will get the results you want if you ask for a^i mod a^3+a+1;.

Alternately, specific for your finite field example, you can put F<a> := GF(2^3); which you can verify is constructed with $x^3+x+1$ as the minimal polynomial for a (ask for DefiningPolynomial(F);). By default, Magma will print elements of F as powers of a, but if you put in the command SetPowerPrinting(F,false); it will give you a reduced polynomial in a instead. So then you can just type a^i; and it will return this field element as the remainder when divided by $a^3+a+1$.

(Note that if you type both F<a> := GF(2^3); and P<a> := PolynomialRing(F); then you have introduced some confusion as to whether a is a finite field element, or an indeterminate in your polynomial ring. You should really avoid doing this.)

I managed to make the program.

F<a>:=GF(2^3);
P<a>:=PolynomialRing(F);

function f(x)
return x^5;
end function;

A:=[];
for i in [1..6] do
Append(~A, (a^i mod (a^3+a+1)));
end for;

A:=Reverse(A);
A:=Append(A,1);
A:=Append(A,0);

A:=Reverse(A);

F:=[];
for i in [1..6] do
Append(~F,((f(a))^i mod (a^3+a+1)));
end for;

F:=Reverse(F);
F:=Append(F,1);
F:=Append(F,0);

F:=Reverse(F);

BinA:=[];
for i in A do
for j in [a^2,a,1] do
if j in Terms(i) then
Append(~BinA,1);
else
Append(~BinA,0);
end if;
end for;
end for;

BinA:=Matrix(3,BinA);

BinF:=[];
for i in F do
for j in [a^2,a,1] do
if j in Terms(i) then
Append(~BinF,1);
else
Append(~BinF,0);
end if;
end for;
end for;

print BinF;


conditional probability problem A prerequisite for students to take a probability class is to pass calculus. A
  study of correlation of grades for students taking calculus and probability
  was conducted. The study shows that 25% of all calculus students get an A;
  and that students who had an A in calculus are 50% more likely to get an A
  in probability as those who had a lower grade in calculus. If a student who
  received an A in probability is chosen at random, what is the probability
  that he/she also received an A in calculus?

My Attempt:

I know $\Pr(A\mid B)$ with $A$ being event that the student gets an $A$ in calculus and $B$ being the event that the student gets an $A$ in probability is $\Pr(A \mid B)=\frac{Pr(A, B)}{\Pr(B)}$ but, I can't seem to put the givens into that form.

You know that
$$
P(A|B)=\frac{P(A\cap B)}{P(B)}
$$
and
$$
P(B|A)=\frac{P(A\cap B)}{P(A)}
$$
thus
$$
P(A|B)=\frac{P(A\cap B)}{P(B)}=\frac{P(A|B)P(B)}{P(A)}=\frac{P(A)}{P(B)}P(A| B)
$$

That is a formula for finding P(A|B), but not the only formula.  You should consider using Bayes' theorem, which would allow you to turn probabilities like P(B|A) into your desired P(A|B).


Dense set in the unit circle- reference needed For $x \notin \pi\mathbb Q$, that is, a real $x$ that is not a rational multiple of $\pi$, consider the set $$\{(\cos nx,\sin nx):n = 0,1,2,...\}.$$ It is known that this set is dense in the unit circle $B(0,1)$ of $\mathbb R^2$. Could someone please give me a proof or reference for a proof?

From $x\notin \pi{\mathbb Q}$ it follows that $e^{ikx}\ne1$ for all $k\in{\mathbb Z}\setminus\{0\}$, and this implies that the numbers $e^{inx}\in S^1$ $(n\geq0)$ are all different. Assume that a point $\zeta\in S^1$ and an $\epsilon>0$ is given. Since $S^1$ has finite length we then can find two numbers $n_1<n_2$ with $|e^{in_2x}-e^{in_1 x}|< \epsilon$. Put $n':=n_2-n_1$. Then
$$\bigl|e^{in'x} -1\bigr|=|e^{in_2x}-e^{in_1 x}|<\epsilon\ .$$
Put $n_k:=k\>n'$ $(k\geq0)$. Then the successive points $e^{i n_k x}\in S^1$ $(k\geq0)$ have a distance $<\epsilon$. It follows that there is a $k\geq0$ with $|e^{in_k x}-\zeta|<\epsilon$.

You can proove that every rational number other than 1/2 comes from an irrational angle.

a = cos(pi d/z) + i sin(pi d/z) solves some equation of the form a^z + 1 = 0
Prove that a can never be a rational, by supposing that where

$$a^n = \sum^{z-1}_{e=0} x_i a^e$$

that if a were a fraction p/q, multiply through by p^n, then the LHS is not a multiple of q, and the RHS is, unless q=1.

Therefore the equation a can never be rational unless it is half-integer, which means that the rational numbers arise from irrational angles.

Since the rational numbers are dense on the circle, the irrational angles are too.


Show that $a_n^{1/n}$ converges as $n\to\infty$ Suppose that a sequence ${a_n : n = 1,2,\cdots}$ real numbers is such that
$a_n\geq 1$ for all $n ≥ 1$ and
$$
a_{n+m}\leq a_na_m\quad \rm{for~ all}~n\geq1, m\geq1.
$$
Show that $a_n^{1/n}$ converges as $n\to\infty$

My solution:
By taking log, we have

$$ \log{a_{n+m}}\leq \log{a_na_m}=\log{a_n}+\log{a_m}\quad \rm{for~ all}~n\geq1, m\geq1.
$$

So we have
\begin{align}
\log{a_2}&\leq \log{a_1}+\log{a_1}=2\log{a_1}
\\
\log{a_3}&\leq \log{a_1}+\log{a_2}\leq3\log{a_1}
\\
\cdots
\\
\log{a_n}&\leq n\log{a_1}
\end{align}
So,
$$
\log{a_n}^{1/n}=\frac{1}{n}\log{a_n}
$$
So I can prove $\log a_n$ is bounded but cannot to prove it's monotonic which can sufficiently lead to $\log a_n$ converges. How to deal with it?

Or if we cannot prove monotonic, how to prove the limit exists?

we have
$$a_{n+m}\leq a_na_m\quad $$
taking m=n,  we get
$$a_{2n}\leq a_n^2\quad $$

taking square roots on both sides, we get

$$ a_{2n}^{1/2}\leq a_n\quad$$

taking $n^{th}$ roots on both sides , we get

$$ a_{2n}^{1/2n}\leq a_n^{1/n}\quad$$

let

$$f(n)=a_n\quad$$

then , we have
$$f(2n)\leq f(n)\quad$$

which is a monotic decreasing sequence and hence converges


expected value for max of a set of random variables we randomly pick $M$ elements from a set of $N$ real numbers, $A=\{ a_1,a_2,\ldots,a_N \}$. Then we sort these $M$ numbers, what is the expected value for the largest element?  (let say $N=1000000$, $M=1000$), I am interested in the solution for general $A$, and/or the case that elements of $A$ are taken from a normal distribution.

Note:  Since you're concerned with subsets, I'm going to assume that you're choosing your elements without repetition.  As per your question, I'll also assume that you're picking your elements with uniform probability (ie completely at random).

Adding a bit of notation, suppose that our chosen subset is $B=\{b_1,b_2,\cdots,b_M\}$ with $b_1<b_2<\cdots <b_M$.  If we assume also that $a_1<a_2<\cdots<a_N$, then clearly $P(b_M<a_M)=0$, since the smallest $M$ elements that we can choose from $A$ are $\{a_1,a_2,\cdots,a_M\}$.

Now, $P(b_M=a_M)=\frac{1}{{N \choose M}}$, since the only possible such subset is $\{a_1,a_2,\cdots, a_M\}$.

To compute $P(b_M=a_{M+1})$, the only way this can happen is if $\{b_1,\cdots, b_{M-1}\}\subset \{a_1,a_2,\cdots, a_M\}$, hence $P(b_M=a_{M+1})=\frac{{M \choose M-1}}{{N \choose M}}$.

And by a similar argument, for $1\leq i \leq N-M$, $P(b_M=a_{M+i})=\frac{{M +(i-1) \choose {M-1}}}{{N \choose M}}$.

So, from there, the expected value is $$\frac{1}{{N \choose M}}\sum\limits_{i=0}^{N-M}a_i {{M+(i-1)} \choose {M-1}}$$

Hint 1: For every nonnegative random variable $X$, $\mathrm E(X)=\int\limits_0^{+\infty}\mathrm P(X\geqslant x)\mathrm dx$.

Hint 2: If $M=\max\{\xi_1,\xi_2,\ldots,\xi_n\}$, then, for every $x$, $[M\leqslant x]=\bigcap\limits_{k=1}^n[\xi_k\leqslant x]$.


Solve $a^2 - 2b^2 - 3 c^2 + 6 d^2 =1 $ over integers $a,b,c,d \in \mathbb{Z}$ Are we able to completely solve this variant of Pell equation?
$$ x_1^2 - 2x_2^2 - 3x_3^2 + 6x_4^2 = 1 $$
This has an interpretation as is related to the fundamental unit equation of $\mathbb{Q}(\sqrt{2}, \sqrt{3}) = \mathbb{Q}[x,y]/(x^2 - 2, y^2 - 3)$ as well as various irreducible quartics.  Is this the same as solving three separate Pell equations?

\begin{eqnarray*}
x^2 - 2y^2 &=& 1 \\
x^2 - 3y^2 &=& 1 \\
x^2 + 6y^2 &=& 1 \tag{$\ast$}
\end{eqnarray*}

Our instinct suggests there should be three degrees of freedom here, and setting different variables to zero we could find three two of these (the third equation has no solutions over $\mathbb{R}$). Does that generate all the solutions?

Perhaps I should remark this quadratic form is also a determinant

$$  a^2 - 2b^2 - 3c^2 + 6d^2 = \det \left[
\begin{array}{cc}
a + b \sqrt{2} & c - d \sqrt{2}\\
3(c + d \sqrt{2}) & a - b \sqrt{2}
\end{array}
 \right]$$

This might not even contain Oscar's solution.  Extending Keith's solution We could have:

$$
\left[
\begin{array}{cc}
a + b \sqrt{2} & c - d \sqrt{2}\\
3(c + d \sqrt{2}) & a - b \sqrt{2}
\end{array}
 \right] =
\left[
\begin{array}{cc}
3 + 1 \sqrt{2} & 2 - 1 \sqrt{2}\\
3(2 + 1 \sqrt{2}) & 3 - 1 \sqrt{2}
\end{array}
 \right]^n
 $$


Prove without Liouville's theorem: $f$ is entire, $\forall z \in \mathbb C: |f(z)| \leq |z|$, then $f=a \cdot z$, $a \in \mathbb C, |a| \leq 1$ Prove without Liouville's theorem: $f$ is entire, $\forall z \in \mathbb C: |f(z)| \leq |z|$, then $f=a \cdot z$, $a \in \mathbb C, |a| \leq 1$

What I tried so far: $f$ is entire, so $f(z)= \Sigma _{n=0}^\infty a_nz^n$, and then $|\Sigma _{n=0}^\infty a_nz^n| \leq |z| \Rightarrow |\frac {\Sigma _{n=0}^\infty a_nz^n}{z}| \leq 1 \Rightarrow |\Sigma _{n=0}^\infty a_nz^{n-1}| \leq 1$

How can I continue from here?

Thank you in advance for your assistance!

Note that $|f(z)| \leq |z|$ implies $|f(0)| \leq |0|$ and thus $f(0) = 0$. If $f(z) = \sum \limits _{n=0} ^\infty a_n z^n$, this means that $a_0 = 0$, so $f(z) = z g(z)$, where $g(z) = \sum \limits _{n=1} ^\infty a_n z^{n-1}$. By hypothesis, you get $|g(z)| \leq 1$. Now, you don't want to use Liouville's theorem, so we turn to Cauchy's inequality: for any $r>0$ and $n>1$ we have $|a_{n+1}| = |g ^{(n)} (0)| \leq {\sup \limits _{|z| = r} |g(z)| \over r^n} = {1 \over r^n}$. Since $r>0$ may grow arbitrarily large, this shows that $a_{n+1}$ may get arbitrarily small when $n>1$, and thus $a_{n+1} = 0$ for $n>1$. So, $f(z) = a_0 + a_1 z$. But we have proved right at the beginning that $a_0 = 0$, so $f(z) = a_1 z$.

Possible answer:

Set $g(z)=\frac {f(z)}{z}$ for $z \neq 0$ and $g(z)=A, A \in \mathbb C$ for $z=0$. So we get that $g(z)$ is entire. Let there be some $z_0 \in \mathbb C$, and circle with radius $R$ centered in $z_0$, $C_R$. So by Cauchy Integral Formula:

$g'(z_0)= \frac {1}{2 \pi i} \int_{C_R} \frac{g(z)}{(z-z_0)^2}$

$$|g'(z_0)|= |\frac {1}{2 \pi i} \int_{C_R} \frac{g(z)}{(z-z_0)^2}| =  |\frac {1}{2 \pi i} \int_{C_R} \frac{ \frac {f(z)}{z}}{(z-z_0)^2}|= |\frac {1}{2 \pi i} \int_{C_R} \frac{f(z)}{z(z-z_0)^2}| \leq \frac {1}{2 \pi } \cdot 2 \pi R \cdot \frac {1}{R^2} \cdot max_{z \in C_R}|\frac {f(z)}{z}|= \frac {1}{R}\cdot 1= \frac {1}{R} $$

So we'll take circle $C_R$ with infinite radius, and we get that $g'(z_0)=0$ for every $z_0$, so $g(z)$ is constant. So $g(z)=a$ for some $a \in \mathbb C$, so $f(z)=a \cdot z$, and $|a| \leq 1$.


Prove that if $ p | x^p + y^p $ where $p$ is a prime number greater than $2$, then $p^2 | x^p + y^p$ I was trying to solve the following problem recently:

Prove that if $ p | x^p + y^p $ where $p$ is a prime number greater than $2$, then $p^2 | x^p + y^p$. Here $x$ and $y$ are both integers.

$a|b$ reads $a$ divides $b$ or $b$ is divisible by $a$.

I was able to solve the problem, but through arguably tedious means, my solutions is here.

I feel like there are more elegant solutions available, but I cannot think of any at present, which is why I decided to post this as a question here.

Thanks

Using Fermat's Little Theorem,

$$a^p\equiv a\pmod p$$ for any integer $a$

$$p|(x^p+y^p)\iff p\mid(x+y)$$

Let $x+y=kp$

For odd prime $p,$

$$x^p+y^p=x^p+(kp-x)^p=x^p-(x-kp)^p=\binom p1x^{p-1}\cdot kp+\text{ terms divisible by }p^2$$
$$\equiv0\pmod{p^2}$$

$p|x^p+y^p$ given

since $p$ is a prime number $> 2$, it is an odd prime number

For any odd power $p$, $x^p+y^p$ has a factor $(x+y)$

Using Fermat's little theorem

$$x^p \equiv x \mod p\\
y^p \equiv  y\mod p\\
x^p+y^p \equiv (x+y) \equiv 0\mod p$$  since $p|x^p+y^p$

Therefore $p|(x+y)$, so $(x+y) = m*p$ where $m$ is an integer

$p|x^p+y^p$ and $(x+y)|x^p+y^p$

we can say $x^p+y^p = k*p*(x+y)$ where k is an integer
$=k*p*m*p = kmp^2$

So $x^p+y^p= kmp^2$ where $k$ and $m$ are integers.

so $p^2|x^p+y^p$

Proved


do i treat (y) as a variable or as a constant when differentiating dy/dx I want to find $\left(\dfrac{dy}{dx}\right)$ for :  $x^3 +y^3=6xy$ ,i don't understand when diff $(y^3)$ do i treat it like a constant or do i treat it like a term?

It helps to remember here that you're ASSUMING that there's a function, which I'll call $Y$ to keep things distinct, such that
$$
x^3 + Y(x)^3 = 6 \cdot x \cdot Y(x)
$$
and since the expressions on the left and right side of the equality both are functions of $x$, you can differentiate them. For the right hand side, for instance, you get
$$
deriv = 6 Y(x) + 6x Y'(x)
$$
But this is almost always written
$$
deriv = 6y + 6x \frac{dy}{dx}
$$
completely hiding the dependence of $Y$ on $x$.

Think of it as separating all the elements dependent on x being represented as functions (i.e. assuming those functions differentiable at x) . Then take the limit for each change in function ($\Delta(f(x)$) as $\Delta$x->0 which then will just work as simple fractions instead of lagrange's notation.

$$\lim\limits_{\Delta x \to 0} \frac{\Delta f(x)}{\Delta x}$$

So for the a
g(x) = $x^3$
and h(y) = $y^3$

So it becomes $\frac{\Delta g(x)}{\Delta x}$ + $\frac{\Delta h(y)}{\Delta y} * \frac{\Delta y}{\Delta x}$

and taking the limit will give you $\frac{dy}{dx}$


Show $\frac{1}{x^{2}}$ is not uniformly continuous on (0,5]. Show g(x) = $\frac{1}{x^{2}}$ is not uniformly continuous on (0,1.5].

attempt

g(x) is not uniformly continuous if
$$\exists \epsilon > 0 : \forall m > 0 \exists x,y \epsilon (0,1.5]  |x-y| < m, |g(x)-g(y)| \geq \epsilon$$

$ |g(x)-g(y)| = |\frac{1}{x^{2}} - \frac{1}{y^{2}}| = |\frac{y^{2}-x^{2}}{x^{2}y^{2}}|$
$$$$
$=\frac{|x^{2}-y^{2}|}{x^{2}y^{2}} = \frac{|x-y||x+y|}{x^{2}y^{2}} = \frac{|x-y||x-y+2y|}{x^{2}y^{2}} \geq \frac{|x-y|(|x-y|-2|y|)}{x^{2}y^{2}} = \frac{|x-y|(1-2|y|)}{x^{2}y^{2}}$ if m = 1
$$$$
and if $\frac{|x-y|(1-2|y|)}{x^{2}y^{2}}$ is to be made less than $\epsilon$ then $|x-y|) < \frac{x^{2}y^{2}\epsilon}{(1-2|y|}$ and since $x^{2}y^{2}$ is smaller and smaller for x and y close to 0, no single number m workds for all x and y and so g(x) = $\frac{1}{x^{2}}$ is not uniformly continuous on (0,1.5].

Let $\epsilon =1$, assume to get contradiction that $g(x)=\frac{1}{x^2}$ is uniformly continuous on $(0,1.5]$. By the assumption exists $\delta > 0$ s.t. $\forall x,y\in (0,1.5],\mid x-y\mid<\delta \Rightarrow \mid g(x)-g(y) \mid <\epsilon$. Let us observe the following series, $x_n=\frac{1}{n}$ and $y_n=\frac{1}{2n}$. It is easy to see that $\mid x_n-y_n\mid=\mid \frac{1}{n}-\frac{1}{2n}\mid=\mid \frac{1}{2n}\mid \xrightarrow{n\rightarrow \infty} 0$ thus for a large enough $n$ we have $\mid x_n-y_n\mid<\delta$. But we also have $\mid g(x_n)-g(y_n)\mid=\mid \frac{1}{(\frac{1}{n})^2}-\frac{1}{(\frac{1}{2n})^2}\mid=\mid n^2-4n^2\mid=3n^2\xrightarrow{n\rightarrow \infty}\infty$. For large enough $n$ we have $\mid x_n-y_n\mid<\delta$ and $\mid g(x_n)-g(y_n)\mid >1=\epsilon$

Perhaps I'm greatly mistaken, but I believe that it IS uniformly continuous on (0,1.5], Since f(x) is (in the usual sense) continuous on (0,1.5], and (0,1.5] is compact, then f(x) is uniformly continuous on (0,1.5].  (This is a basic theorem regarding uniform continuity and compactness)


Finding Inverse Laplace Transform using Taylor Series Find the inverse Laplace transform

$F(t)=\mathcal{L}^{-1}(s^{-\frac{1}{2}}e^{-\frac{1}{s}})$

using each of the following techniques:

Expand the exponential in a Taylor series about s=∞, and take inverse Laplace transforms term by term (this is allowable since the series is uniformly convergent.).
Sum the resultant series in terms of elementary functions.


Greatest Lower Bound in $\mathbb{R}$ as a corollary of the LUB? I can assume as fact that $\mathbb{R}$ is an ordered field in which every non-empty subset that is bounded above has a least upper bound.

My question is whether I can also assume as fact that every non-empty subset that is bounded below also has a greatest lower bound. I'm trying to show that if $A,B \subseteq \mathbb{R}$, and $A,B \neq \emptyset$, then there exists a least upper bound for $A$ (I've proven this), and a greatest lower bound for $B$ (this is what I'm currently concerned with).

Any tips, or helpful definitions?

HINT: If $A\subseteq\Bbb R$ is bounded below, then $-A=\{-a:a\in A\}$ is bounded above.

Alternative HINT: Let $B$ be the set of lower bounds for $A$. $B$ is bounded above, and its supremum is ... ?

Yes, if every nonempty set that is bounded above has a least upper bound, then every nonempty set that is bounded below has a greatest lower bound. I know of two different ways to prove this.

Suppose $B$ is nonempty and bounded below. Then the set $-B=\{-x:x\in B\}$ is nonempty and bounded above, so it has a least upper bound, call it $u$. Then $-u$ is the greatest lower bound of $B$.
Never mind, just read Brian's answer!


2 seemingly isomorphic groups Take the following two groups:
$G_1$
$$\begin{array}{c|c|c|c|c}
 \cdot & e
 & a & b& c\\\hline
 e & e                                       & a    & b   & c \\\hline
 a &a                                      & e  & c&  b\\\hline
 b & b                                       & c    & e & a \\\hline
 c & c                                       & b & a & e
\end{array}$$
$G_2$
$$\begin{array}{c|c|c|c|c}
 \cdot & e
 & a & b& c\\\hline
 e & e                                       & a    & b   & c \\\hline
 a &a                                      & e  & c&  b\\\hline
 b & b                                       & c    & a& e \\\hline
 c & c                                       & b & e&a
\end{array}$$
In $G_1$ there are 3 normal subgroups, $\{e,a\},\{e,b\},\{e,c\}$
Each one leading to isomorphicly equivalent factor groups.
$$G_1 \cong \mathbb{Z} / 2\mathbb{Z} \times  \mathbb{Z} / 2\mathbb{Z} $$
$G_2$ has one normal subgroup $\{e,a\}$ which leads to
$$G_2 \cong \mathbb{Z} / 2\mathbb{Z} \times \mathbb{Z} / 2\mathbb{Z} $$
Which seems to imply there is an isomorphism between them, but there clearly isn’t.
Where am I wrong?

In$G_2$ we have $c=b^{-1}$ and $c^2=a$ so that $b^{-2}=a=b^2$, and hence $b^4=e$, but $b^2=a\neq e$. Hence $G_2$ has an element of order $4$, so that $G_2\cong C_4$, and hence is not isomorphic to $C_2\times C_2\cong G_1$.

No reason to think the groups are isomorphic.
In fact, they have different "identity-skeletons", so can't be.


How many ways in which distinct people can get off a train I've been learning probability recently but I'm having trouble solving this question:

Suppose you have 50 people on a train and you have 4 stations you can get off at (call them Stations 1,2,3,4). If no one boards the train at any of these stations, in how many ways can the 50 people get off the train, assuming the people are distinguishable (I care who gets off where)?

If I didn't care who gets off where, then using stars and bars it would simply be 54 choose 3. But the problem for me arises in thinking when they're distinguishable. Right now my logic was for each of the 54 choose 3 ways, you can permute the groups among themselves in 4! ways. I'm pretty sure that's not right, but I don't know where to go.

We are counting the functions $f$ from a set of size $50$ to $\{1,2,3,4\}$.
To see this, for any person $p$ let $f(p)$ be the station she gets off at.

There are $4^{50}$ such functions.

This is a problem of the form $x_1 + \dots + x_k = n$, where $k=4$ and $n=54$. A typical ball-picking problem, which is unordered and with replacement. The answer is therefore

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

More information here: http://mathworld.wolfram.com/BallPicking.html .


Simple Combinations Binomial There is a little sum I am stuck with.

Find the value of
$${1 \choose 0}+{4 \choose 1}+{7 \choose 2} +\ldots+{3n+1 \choose n}$$

where ${n \choose r}$ is the usual combination.

A little hint will be fine.

Find the coefficient of $x^{0}$ in $\displaystyle  (1+x)+\frac{(1+x)^{4}}{x}+\frac{(1+x)^{7}}{x^{2}}+\ldots$
It's forming a geometric series.


Scalar Multiplication, why do I keep getting this bizarre result? I have two vectors, u and v
u = [2/5,-1,1/5]
v = [-1,5/2, -1/2]

I need to prove that they are Scalar of one another, and in such a way that  u = kv

k being the scalar variable.

The intuitive method would be to look at it and see what happens when you multiply 2/5 by v and suddenly it equals u.

However, I want to do things by the book and FIND the scalar multiple using math.

So, I do the standard formula (u*v)/|v|

However, I keep getting -3/(sqrt(30))/2

Which doesn't line up with the actual result.

What I have tried:

u*v is just a dot product, right? So that ends up giving you -(2/5) + -(5/2) + -(1/10) which ends up being -30/10 = -3.

Now the denominator which is magnitude v or |v| which is sqrt((-1)^2 + (5/2)^2 + (-1/5)^2) which netted me sqrt(30)/2, this isn't the result that I need or that mathlab says is correct, a little help would go a long way here.

You say that you want to "find the scalar using math."

$u = (u_1,u_2, u_3) , v = (v_1,v_2, v_3)$

It is given that one vector is a scalar multiple of the other.

$u = \lambda v\\
\lambda = \frac {u_1}{v_1} = \frac {u_2}{v_2} = \frac {u_3}{v_3}$

Is a perfectly valid approach "using math"

If "by the book," means using the dot product...

$u = \lambda v\\
u\cdot v = \lambda v\cdot v = \lambda \|v\|^2\\
\lambda = \frac {u\cdot v}{\|v\|^2}$

$\lambda = \frac {-\frac {2}{5} - \frac {5}{2} - \frac {1}{10}}{1 + \frac {25}{4} + \frac 14} = -\frac {2}{5}$

Multiplying the first vector by the scalar $-\frac{5}{2}$ yields the second vector.

$u = kv$

So $$k = \frac{-1}{(\frac{2}{5})} = \frac{(\frac{5}{2})}{-1} = \frac{-(\frac{1}{2})}{(\frac{1}{5})} = -\frac{5}{2}$$


About Exact Differentials This is an excerpt from my textbook: Consider the general differential containing two variables, where $f = f(x,y)$,
$$
d f=A(x, y) d x+B(x, y) d y
$$
We see that
$$
\frac{\partial f}{\partial x}=A(x, y), \quad \frac{\partial f}{\partial y}=B(x, y)
$$
and, using the property $f_{x y}=f_{y x},$ we therefore require
$$
\frac{\partial A}{\partial y}=\frac{\partial B}{\partial x}
$$
This is in fact both a necessary and a sufficient condition for the differential to be exact.
I see why this is a necessary condition, but why is it a sufficient condition?

Assume that $A,B $ and its first order partial derivatives are continuous on a simply connected open set $D$.
Given $\frac{\partial A}{\partial y}=\frac{\partial B}{\partial x}$, if there exists a function $h(x,y)$ such that $d(h(x,y))=Adx+Bdy\tag{A}$, then we are done.
Let's denote $h(x,y)$ by $h$.
Consider, $\frac{\partial h }{\partial x}=A$ and $\frac{\partial h }{\partial y}=B$. Let $(a,b)$ and $(x,y)\in D$
From $\frac{\partial h }{\partial x}=A$, we have : $h=\int_{x=a}^{x} A\partial x+g(y)\tag{1}$
Therefore, by $\frac{\partial h }{\partial y}=B$, we get $\frac{\partial  }{\partial y}(\int_{x=a}^{x} A\partial x)+g'(y)=B\implies \int_{x=a}^{x}\frac{\partial  }{\partial y}A \partial x+g'(y)=B\implies g'(y)=B-\frac{\partial  }{\partial x}(\int_{x=a}^{x}B\partial x)=B-B(x,y)+B(a,y)=B(a,y)\tag{2}$

So, we have now shown that $g'(y)$ is free of $x$, that is we can find $g(y)$ from $(2)$ using FTC. $g(y)=g(b) +\int_{y=b}^{y} g'(y) dy=g(b) +\int_{y=b}^{y} B(a,y) dy$. So now $g(y)$ is known.
We'll put this $g(y)$ into $(1)$ and we'll have known $h$. And clearly the way $h$ was constructed implies that $(A)$ is satisfied by $h$.

I think the misunderstanding here comes from the language used, and not so much the differential calculus (might want to tag this as "logic" or something). This is a good resource to understand what necessary and sufficient mean in logic, separately and together.
The most useful thing you can do to better understand these is think of counter examples: what is something that is necessary but not sufficient? A good example from that page is the following.
P: Oxygen exists in the atmosphere.
Q: Humans exist.
Clearly P is necessary for Q. Having oxygen in the earth's atmosphere is a necessary condition for human life. Crucially, though, having oxygen will not guarantee human life – there are many other conditions needed for human life other than oxygen in the atmosphere. In this way, P is necessary but not sufficient for Q.
Now consider this example.
P: All men are mortal.
Q: Socrates was mortal.
In this case, P being true always means Q is true (we all know Socrates was a man). There is no possible way P could be true without Q being true. Equally, Q couldn't be true without P being true. P is necessary and sufficient for Q.
TLDR:

P necessary and sufficient for Q = P $\Leftrightarrow$ Q,
P necessary but not sufficient for Q = Q $\Rightarrow$ P,
P not necessary but sufficient = logically invalid.

What your textbook is saying, then, is that that condition implies necessarily the exactness of the differential.


What does $\text{rank}(AB) = \text{rank}(A)$ imply? Suppose now I have two matrices $A$ and $B$ which are of size $m\times n$ and $n\times l$ respectively. For simplicity, assume $n<m<l$.

Assume that I have $\text{rank}(AB) = \text{rank}(A) \ne \text{rank}(B)$. Then can I conclude that the matrix $B$ will have full row rank $n$?

I know there is a special case that when $\text{rank}(A) = \text{rank}(B)$, for example the simplest case that the matrices are zero matrices, then the conclusion is not correct. So I would exclude this case. I am wondering that if I exclude the special case, is the conclusion above correct?

It implies $rank(B)$ is at least $rank(A)$. Since the rank of the matrix is the dimension of its image, then $\dim A(B(\mathbb{R}^\ell)) \leq \dim B(\mathbb{R}^\ell)$, hence $rank(AB) \leq rank(B)$.

As noted in the comments, you cannot deduce that $B$ is full rank.

Consider $$A = \begin{pmatrix} 1 & 0 & 0\end{pmatrix}, B = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{pmatrix}$$

Then $$AB = \begin{pmatrix} 1 & 0 & 0 \end{pmatrix}.$$

Hence $AB = A$, in particular $Rank(AB) = Rank(A)$. But $Rank(B) = 2 <3$.

Edit, another example:

For some reason, we want to consider $A$ $m \times n$ and $B$ $n \times \ell$ will $n < m < \ell$.

Let $$A = \begin{pmatrix} 0 & 0 \\ 0 & 0 \\ 0& 0 \end{pmatrix}, B = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 &0 \end{pmatrix}$$

Then $A$ is rank 0, $AB$ rank 0, $B$ rank 1 < 2.


Measurable set in real numbers with arbitrary lebesgue density at some point I'm not sure if this is easy or not, but i can't see the solution (or that it is wrong!)

Suppose that $\alpha \in (0,1)$ is given, Can you find a Lebesgue measurable set in $\mathbb{R}$, such that at point $0$, it has Lebesgue density $\alpha$?

Let $\alpha _n =\alpha \{\frac 1 n -\frac 1 {n+1}\}$ and choose a subset $E_n$ of $ (\frac 1 {n+1},\frac 1 n) \cup (-\frac 1 n,-\frac 1 {n+1})$ whose measure is $\alpha _n$. Let E be the union of the sets $E_n$. Then E has density $\alpha$.


Why study Algebraic Geometry? I'm going to start self-stydying algebraic geometry very soon. So, my question is why do mathematicians study algebraic geometry? What are the types of problems in which algebraic geometers are interested in? And what are some of the most beautiful theorems in algebraic geometry?

NEW ADDITION: a big list of freely available online courses on algebraic geometry, from introduction to advanced topics, has been compiled in this other answer. And a digression on motivation for studying the subject along with a self-learning guide of books is in this new answer.

There are other similar questions, above all asking for references for self-studying, whose answers may be helpful:

(Undergraduate) Algebraic Geometry Textbook Recomendations.
Reference for Algebraic Geometry.
Best Algebraic Geometry text book? (other than Hartshorne).

My personal recommendation is that you start and get your motivation in the following freely available notes. They are extremely instructive, from the very basics of complex algebraic curves up to schemes and intersection theory with Grothendieck-Riemann-Roch, and prove of some of the theorems I mention below. They are excellent for self-study mixing rigor with many pictures! (sadly, something quite unusual among AG references):

Matt Kerr - Lecture Notes Algebraic Geometry III/IV, Washington University in St. Louis.
Andreas Gathmann - Class Notes: Algebraic Geometry, University of Kaiserslautern.

For a powerful, long and abstract course, suitable for self-study, these notes have become famous:

Ravi Vakil - Foundations of Algebraic Geometry, Stanford University.

Also, there are many wonderful lecture videos for complete courses on elementary algebraic geometry, algebraic surfaces and beyond, by the one old master:

Miles Reid - Lecture Courses on Video (WCU project at Sogang University),

where you can really start at a slow pace (following his undergraduate textbook) to get up to the surface classification theorem.

Now, Algebraic Geometry is one of the oldest, deepest, broadest and most active subjects in Mathematics with connections to almost all other branches in either a very direct or subtle way. The main motivation started with Pierre de Fermat and René Descartes who realized that to study geometry one could work with algebraic equations instead of drawings and pictures (which is now fundamental to work with higher dimensional objects, since intuition fails there). The most basic equations one could imagine to start studying were polynomials on the coordinates of your plane or space, or in a number field in general, as they are the most basic constructions from the elementary arithmetic operations. Equations of first order, i.e. linear polynomials, are the straight lines, planes, linear subspaces and hyperplanes. Equations of second order turned out to comprise all the classical conic sections; in fact the conics classification in the affine, Euclidean and projective cases (over the real and complex numbers) is the first actual algebraic geometry problem that every student is introduced to: the classification of all possible canonical forms of polynomials of degree 2 (either under affine transformations or isometries in variables $(x,y)$, or projective transformations in homogeneous variables $[x:y:z]$). Thus the basic plane curves over the real numbers can be studied by the algebraic properties of polynomials. Working over the complex numbers is actually more natural, as it is the algebraic closure of the reals and so it simplifies a lot the study tying together the whole subject, thanks to elementary things like the fundamental theorem of algebra and the Hilbert Nullstellensatz. Besides, working within projective varieties, enlarging our ambient space with the points at infinity, also helps since then we are dealing with topologically compact objects and pathological results disappear, e.g. all curves intersect at least at a point, giving the beautiful Bézout's theorem.

From a purely practical point of view, one has to realize that all other analytic non-polynomial functions can be approximated by polynomials (e.g. by truncating the series), which is actually what calculators and computers do when computing trigonometric functions for example. So when any software plots a transcendental surface (or manifold), it is actually displaying a polynomial approximation (an algebraic variety). So the study of algebraic geometry in the applied and computational sense is fundamental for the rest of geometry.

From a pure mathematics perspective, the case of projective complex algebraic geometry is of central importance. This is because of several results, like Lefschetz's principle by which doing (algebraic) geometry over an algebraically closed field of characteristic $0$ is essentially equivalent to doing it over the complex numbers; furthermore, Chow's theorem guarantees that all projective complex manifolds are actually algebraic, meaning that differential geometry deals with the same objects as algebraic geometry in that case, i.e. complex projective manifolds are given by the zero locus of a finite number of homogeneous polynomials! This was strengthened by Jean-Pierre Serre's GAGA theorems, which unified and equated the study of analytic geometry with algebraic geometry in a very general setting. Besides, in the case of projective complex algebraic curves one is actually working with compact orientable real surfaces (since these always admit a holomorphic structure), therefore unifying the theory of compact Riemann surfaces of complex analysis with the differential geometry of real surfaces, the algebraic topology of 2-manifolds and the algebraic geometry of algebraic curves! Here one finds wonderful relations and deep results like all the consequences of the concept of degree, index and curvature, linking together the milestone theorems of Gauß-Bonnet, Poincaré-Hopf and Riemann-Roch theorem! In fact the principal classification of algebraic curves is given in terms of their genus which is an invariant proved to be the same in the different perspectives: the topological genus of number of doughnut holes, the arithmetic genus of the Hilbert polynomial of the algebraic curve and the geometric genus as the number of independent holomorphic differential 2-forms over the Riemann surface. Analogously, the study of real 4-manifolds in differential geometry and differential topology is of central importance in mathematics per se but also in theoretical and mathematical physics, for example in gauge theory, so the study of complex algebraic surfaces gives results and provides tools. The full birational classification of algebraic surfaces was worked out decades ago in the Kodaira-Enriques theorem and served as a starting point to Mori's minimal model program to birationally classify all higher-dimensional (projective) complex algebraic varieties. A fundamental difference with other types of geometry is the presence of singularities, which play a very important role in algebraic geometry as many of the obstacles are due to them, but the fundamental Hironaka's resolution theorem guarantees that, at least in characteristic zero, varieties always have a smooth birational model. Also the construction and study of moduli spaces of types of geometric objects is a very important topic (e.g. Deligne-Mumford construction), since the space of all such objects is often an algebraic-geometric object itself.
There are also many interesting problems and results in enumerative geometry and intersection theory, starting from the classic and amazing Cayley-Salmon theorem that all smooth cubic surfaces defined over an algebraic closed field contain exactly 27 straight lines, the Thom-Porteus formula for degeneracy loci, Schubert calculus up to modern quantum cohomology with Kontsevich's and ELSV formulas; Torelli's theorem on the reconstruction of algebraic curves from their Jacobian variety, and finally the cornerstone (Grothendieck)-Hirzebruch-Riemann-Roch theorem computing the number of independent global sections of vector bundles, actually their Euler-Poincaré characteristics, by the intersection numbers of generic zero loci of characteristic classes over the variety.

Besides all this, since the foundational immense work of Alexandre Grothendieck, the subject has got very solid and abstract foundations so powerful to fuse algebraic geometry with number theory, as many were hoping before. Thus, the abstract algebraic geometry of sheaves and schemes plays nowadays a fundamental role in algebraic number theory disguised as arithmetic geometry. Wondeful results in Diophantine geometry like Faltings theorem and Mordell-Weil theorem made use of all these advances, along with the famous proof of Wiles of Fermat's last theorem. The development of abstract algebraic geometry was more or less motivated to solve the remarkable Weil conjectures relating the number of solutions of polynomials over finite number fields to the geometry of the complex variety defined by the same polynomials. For this, tremendous machinery was worked out, like étale cohomology. Also, trying to apply complex geometry constructions to arithmetic has led to Arakelov geometry and the arithmetic Grothendieck-Riemann-Roch among other results.

Related to arithmetic geometry, thanks to schemes, there has emerged a new subject of arithmetic topology, where properties of the prime numbers and algebraic number theory have relationships and dualities with the theory of knots, links and 3-dimensional manifolds! This is a very mysterious and interesting new topic, since knots and links also appear in theoretical physics (e.g. topological quantum field theories). Also, anabelian geometry interestingly has led the way to studies on the relationships between the topological fundamental group of algebraic varieties and the Galois groups of arithmetic number field extensions.

So, mathematicians study algebraic geometry because it is at the core of many subjects, serving as a bridge between seemingly different disciplines: from geometry and topology to complex analysis and number theory. Since in the end, any mathematical subject works within specified algebras, studying the geometry those algebras define is a useful tool and interesting endeavor in itself. In fact, the requirement of being commutative algebras has been dropped since the work of Alain Connes and the whole 'new' subject of noncommmutative geometry has flourished, in analytic and algebraic styles, to try to complete the geometrization of mathematics. On the other hand it attempts to give a quantum counterpart to classical geometries, something of extreme interest in fundamental physics (complex algebraic geometry and noncommutative geometry appear almost necessarily in one way or another in any attempt to unify the fundamental forces with gravity, i.e. quantum field theory with general relativity; even abstract and categorical algebraic geometry play a role in topics like homological mirror symmetry and quantum cohomology, which originated in physics).

Therefore, the kind of problems mathematicians try to solve in algebraic geometry are related to much of everything else, mostly: anything related to the classification (as fine as possible) of algebraic varieties (and schemes, maybe someday), their invariants, singularities, deformations and moduli spaces, intersections, their topology and differential geometry, and framing arithmetic problems in terms of geometry. There are many interesting open problems:

Birational minimal model program for all varieties,
Hodge conjecture,
Jacobian conjecture,
Hartshorne's conjecture,
General Griffiths conjecture,
Fujita's conjecture,
Linearization and cancelation conjectures,
Coolidge-Nagata conjecture,
Resolution of singularities in nonzero characteristic,
Grothendieck's standard conjectures on algebraic cycles,
Grothendieck's anabelian section conjecture,
Classification of vector bundles over projective spaces,
Unirationality of moduli spaces of curves,
Unirationality of rationally connected varieties,
Full rigorous formalization of mirror symmetry and quantum cohomology,
Full theory of a universal cohomology and mixed motives (e.g. Voevodsky vanishing conjecture).

In my personal case, I started as a theoretical physicists but switched completely to pure mathematics because of algebraic geometry, and I also began by self-learning. It is a very deep subject with connections to almost everything else, once one has learned enough to realize that. It is also a very demanding field because of the tremendous background one has to master, in commutative and homological algebra for example, before being able to get to the most modern and interesting results. The effort nevertheless pays off! In fact, the route through commutative algebra actually paves the way not only to algebraic geometry but to algebraic number theory and arithmetic geometry. I had a strong background in differential geometry so I arrived at algebraic geometry through complex (Kähler) geometry, and ended up fascinated by even the most abstract incarnations of it.

"Algebraic geometry seems to have acquired the reputation of being esoteric, exclusive, and very abstract, with adherents who are secretly plotting to take over all the rest of mathematics. In one respect this last point is accurate..." - David Mumford.

So the question could be instead "why not study algebraic geometry!?" I hope this answer motivates you enough to dive into this deep ocean of the mathematical world and to corroborate it yourself. Best luck!

The first chapter of Justin Smith's Introduction to Algebraic Geometry has a nice discussion of Bezout's Theorem and how algebraic geometry approaches geometric problems in general. I think you can download the PDF from the author's web site for free.


Showing that $1 - (1 - b_n)^{a_n} \sim a_n b_n$ as $n \to \infty$. Let $a_n \in \mathbb{N}_{> 0}$ be an increasing sequence and $b_n \in [0,1]$ a decreasing sequence. I am interested in the behavior of the sequence $c_n \triangleq 1 - (1-b_n)^{a_n}$. Intuitively, I know that
\begin{equation*}
1 - (1 - b_n)^{a_n} \sim a_n b_n \quad \text{as $n \to \infty$}.
\end{equation*}
However, I cannot find a rigorous proof for that.

It is easy to upper-bound
\begin{equation*}
1 - (1 - b_n)^{a_n} \le a_n b_n,
\end{equation*}
using the fact that $(1-x)^k \ge 1 - k x$ for $k \ge 1$ and $x$ in vicinity of $0$.

However, I am unable to find a (similar) lower-bound to conclude the claim.

I realized that I should be more clear about what I would like to conclude. In fact, I would like to prove
\begin{equation*}
\lim_{n \to \infty} \frac1n \ln(c_n) = \lim_{n \to \infty} \frac1n \ln(a_n b_n).
\end{equation*}

As pointed out in the answer of Kim Jong Un, we can also lower-bound
\begin{equation*}
1-(1-b_n)^{a_n} \ge a_n b_n (1-b_n)^{a_n-1},
\end{equation*}
which shows,
\begin{equation*}
\frac1n \ln (c_n) \ge \frac1n \ln (a_n b_n) + \frac1n (a_n-1) \ln(1-b_n)
\end{equation*}

Now, if $\limsup_{n\to\infty} a_n b_n < \infty$,
\begin{equation*}
\lim_{n\to\infty} \frac1n (a_n-1) \ln(1-b_n) = 0
\end{equation*}
and we can conclude the claim. However, if $a_n b_n \to \infty$ the lower-bound is not useful.

Maybe logging? $(1-b_n)^{a_n} = e^{a_n \log (1-b_n)} \sim e^{-a_n b_n}$ using Maclaurin series, terms of the form $e^{O(\frac{1}{n})}$ converge to 1.


How to factor numbers that are the product of two primes What are techniques to factor numbers that are the product of two prime numbers? For example, how would we factor $262417$ to get $397\cdot 661$? Would we have to guess that factorization or is there an easier way?

The problem of the factorization is the main property of some cryptograpic systems as RSA.

This fact has been studied for years and nowadays we don't know a algorithm to factorize a big arbitrary number efficiently.

However, if $p*q$ satisfies some propierties (e.g $p-1$ or $q-1$ have a soft factorization (that means the number factorizes in primes $p$ such that $p \leq \sqrt{n}$)), you can factorize the number in a computational time of $O(log(n))$ (or another low comptutational time)

If you are interested in it, you can check this pdf with some famous attacks to the security of RSA related with the fact of factorization of large numbers.

http://www.nku.edu/~christensen/Mathematical%20attack%20on%20RSA.pdf

There is an easier way. The length of prime numbers is not a problem - it is the randomness that lies within.

Let $n=262417$

$397 + 661 = 1058$

$1058 / 2 = 529 = d$

$d^2 = 279841 = a$

Let $s = a - n$

$s = 279841 - 262417 = 17424$ (this square defines distance between $p$ and $q$)

$\sqrt{s} = 132 = t$

$n = p \cdot q$

$n = (d + t)(d - t)$

$n = (529 + 132)(529 - 132) = 661 \cdot 397 = 262417$

To find $s$ you need to know pattern in prime numbers, which will also help you structure semiprime $n$ - "an almost beautiful" arithmetic progression.


Is this olympiad-like question about remainders an open problem? Suppose that we are given two positive integers $x$ and $y$ such that

$$x \mod p \leqslant y \mod p$$

for each prime number $p$. (Here, $x \mod p,\; y \mod p$ stand for the least non-negative residua.) Does it follow that $x = y$?

The problem is seemingly easy as we have to test $x,y$ against finitely many primes only. However, after several attempts I begin to wonder whether this is an open problem...

Note that it seems to be an open problem whether there is a prime number between a pair of squares (a reference would be appreciated), so the case where $x$ and $y$ are squares themselves is hard enough. However, it may well happen that this doesn't require such an argument.

This is a known theorem which is proved in this paper:

a(mod p) ≤ b(mod p) for all Primes p Implies a = b

Authors: P. Erdos, P. P. Palfy and M. Szegedy

The American Mathematical Monthly, Vol. 94, No. 2 (Feb., 1987), pp. 169-170.

Enjoy it!!!

Taking any prime number greater than $x$ and $y$ leads to $x\leq y$.

Now, every $p$ dividing $y$ also divides $x$ because then $x \mod p \leq 0$, thus $y=kx$.

For any prime number $p$ such as $x(k-1)<p<kx=y$ we obtain $y\mod p <x$, with the condition that the primes dividing $k$ also divide $x$.

If we can prove there are always primes in such intervals then we have $x=y$.


what am i misunderstanding here? Dummit and Foote p.161

Let $G$ be an abelian group of order $n>1$.
Let $n={p_1}^{a_1}\cdots {p_k}^{a_k}$ be the prime factorzation.
Then, $G\cong \mathbb{Z}_{{p_1}^{a^1}}\times\cdots\times\mathbb{Z}_{{p_k}^{a^k}}$

Doesn't this mean that there is a unique abelian group of order $n$ up to isomorphism?
What am i misunderstanding here?

The statement in Dummit and Foote says

$$G \cong A_1 \times A_2 \times \dots \times A_k,\text{ where } |A_i| = p_i^{\alpha_i}.$$

It does not say $A_i \cong \mathbb{Z}/p_i^{\alpha_i}\mathbb{Z}$. Indeed, there can be many abelian groups of the same prime-powered order, for example $\mathbb{Z}/p^2\mathbb{Z}$ and $\mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/p\mathbb{Z}$.

The prime factors does not have to be unique.


Proving Prime Integers are countably infinite I've been doing some work with cardinality of sets, and ran into an example I thought was interesting. In proving that the set of prime numbers is a countably infinite set, I've started that showing that the set of prime numbers (integers) $\mathbb{P}$ is a subset of $\mathbb{N}$. Obviously the natural numbers $\mathbb{N}$ can be mapped one-to-one to itself ($1$ to $1$, $2$ to $2$, etc.), so it is a countably infinite set. Following from this, since $\mathbb{P}$ is a subset of a countably infinite set $\mathbb{N}$, then $\mathbb{P}$ must be a countably infinite set as well.

Is this enough information to show $\mathbb{P}$ is a countably infinite set, or must I show a concrete mapping for $\mathbb{P}$?

One way of proving that a subset of $A \subset \Bbb N$ is countably infinite is by demonstrating that it satisfies the following property,

$\tag 1 (\forall F \subset A) \, \bigr[ \, \text{IF } F \text{ if finite THEN } (\exists x \in \Bbb N) \, [x \notin F \text{ and } x \in A] \, \bigr ]$

See also

$\quad$ Subset of a countable set is itself countable

Now let $\mathbb{P}$ denote the set of prime numbers and let $F$ be any finite subset of $\mathbb{P}$.

If $|F| = 0$ then $2 \notin F$ but $2 \in \Bbb P$.

if $|F| = n \gt 0$ then $F = \{p_1,p_2,\dots\,p_n\}$. Set

$\quad \displaystyle {a = (\prod_{1 \le i \le n} p_i) + 1} $

Using Euclidean division one readily shows that $p_i \nmid a$ for any subscript $i$. So if $q$ is any prime factor of $a$ then $q \ne p_i$ for any subscript $i$. So $q \notin F$ but $q \in \Bbb P$.

The above proof 'gears' Euclid's (direct) proof to the OP's requested set theoretic setting.


Limit $\mathop {\lim }\limits_{n \to \infty } n({1 \over {{{(n + 1)}^2}}} + {1 \over {{{(n + 2)}^2}}} + \cdots{1 \over {{{(2n)}^2}}})$ Without using integrals, how to find this limit:

$$\mathop {\lim }\limits_{n \to \infty } {a_n} = n\cdot\left({1 \over {{{(n + 1)}^2}}} + {1 \over {{{(n + 2)}^2}}} + \cdots{1 \over {{{(2n)}^2}}}\right)$$

I tried squeezing the sequence but it didn't workout.
What next should I do?

It's value is equal to $\dfrac{1}{2}$, using definite integral as a limit of sum where $f(x)=\frac{1}{x^2}$.


Why do statisticians like "$n-1$" instead of "$n$"? Does anyone have an intuitive explanation (no formulas, just words! :D) about the "$n-1$" instead of "$n$" in the unbiased variance estimator
$$S_n^2 = \dfrac{\sum\limits_{i = 1}^n \left(X_i-\bar{X}\right)^2}{n-1}?$$

(Too long for a comment:)

I can offer an explanation showing that dividing by $n$ would give an underestimation of the variance. The sum of squares $\sum (X_i - \overline{X})^2$, where $\overline{X}$ is the sample mean, is smaller than the sum $\sum (X_i - \mu)^2$ where $\mu$ is the true mean. This is the case since $\overline{X}$ is expected to be ''closer'' to the data points than the true mean since $\overline{X}$ is calculated based on the data. In fact, $\overline{X}$ is the value of $t$ such that the sum $\sum (X_i - t)^2$ is minimized. This shows that we underestimate the variance, so we should divide by something smaller than $n$. To put it even less formal, you try to determine how much your data is spread by comparing the deviations to the sample mean, which is always an underestimation. The sample mean is as close to the data as possible, whereas the true mean will differ more.

The reason that we divide by precisely $n-1$ is that the estimator becomes unbiased (as pointed out in the comments).

using samples we try to estimate the population mean. But since it is a sample our sample mean would either be more or less than population mean. So squared distance of sample mean from each reading would be higher than that of population. We try to reduce this effect by dividing with a small denominator (N-1) in case of sample variance.


calculating previous k-average Given a number flow  $a_1, a_2, ... a_N$, $N$ is a large number for example $N = 1000$, the goal is to calculate the average value of previous $n$. For example, now we are at state $k$, then if $n = 20$ then $Avg(k) = (a_k + a_{k-1} + ... + a_{k-19})/20$, $k \ge 20$.

1) given an equation to calculate this $Avg(k)$

My answer: $Avg(k) = Avg(k-1) + (a_k - a_{k-n})/n$

2)  Calculate $Avg(k)$ without using substraction

My answer: build an array that has the $Avg(1), Avg(2) ... Avg(k)$, update each one for each step, but it has complexity of $O(Nn)$. Do anybody know an $O(N)$ algorithm for this?

You can keep track of the previous 19 numbers (in a 20 element array), and sum them with the current number, and the replace the oldest number in the array with the current one and move on. To compute the size-$n$ averages for all $N-n$ reasonable slots then takes time $O(Nn)$ as in your solution.

But suppose that instead you keep track of the last 19 numbers, but also keep the sum of the last 1, the next 2, the next 4, the next 8, ... up to the largest power of 2 less than N. You move forward, and now you have the sum of the last 2, the next 2, the next 4, ...which you can update by keeping the last 2, but replaceing the next 2 with the sum of your first two elements, so that you have

last 2, next 4, next 4, next 8, ...

and you can cascade this. And you can tack on the last 1 to the first of the list. In log n time, you've updated this list. In log n time, you can compute the sum of more than half of the previous elements....but computing the sum for the remaining few still takes time O(n/2). But what if you kept a SECOND logarithmic list to help you do that bunch fast as well? Then you'd need to do at most $c * n/4$ work at the end. And so on....

In this manner, you keep $\log n$ lists, each of size $\log n$, and compute the sum in time that looks like (I think) $\log^2 n$, so your overall runtime ends up being $O(N \log^2 n)$. That's not $O(N)$, but it's a good deal better than $O(Nn)$.

The solution for your first question is to keep track of the cumulative sum of the elements in a new array. Now when you are asked to find average of elements between say 'i' and 'j' indices, you can directly get the sum by of elements between these indices by subtracting cumulative sum of 'j' elements from cumulative sum of 'i' elements and divide it by n to get the average. In your case 'i' and 'j' are 'k-n' and 'k' respectively.

Now, time complexity for above algorithm is O(N), because you have to traverse the entire array once and build the cumulative sum array. And the space complexity is O(N), because you have to keep track of cumulative sum of all the elements.

Your second question can be solved by performing subtraction using bitwise operators. Here(https://www.geeksforgeeks.org/subtract-two-numbers-without-using-arithmetic-operators/) is the link to perform subtraction using bitwise operator. Any way time complexity and space complexity will not differ.


Why integration by long division gives different answer than using u substitution? So, after solving this question, I got two different answers? and I don't think it's supposed to be this way?

  Evaluate the integral $$\int \frac{x^2+2}{x+2} dx$$

Using polynomial long division, I get
$$\frac{x^2}2-2x+6\ln|x+2|+C,$$
but using substitution, I get
$$\frac{(x+2)^2}2-4(x+2)+6\ln|x+2|+C.$$

Note that

$$\frac{(x+2)^2}2-4(x+2)+6\ln|x+2|+C=\frac{x^2}2-2x-6+6\ln|x+2|+C=$$

$$=\frac{x^2}2-2x+6\ln|x+2|+(C-6)=\frac{x^2}2-2x+6\ln|x+2|+C_1$$

therefore the two results are the same up to a constant which is not essential, indeed in both cases

$$\frac{d}{dx}\left(\frac{x^2}2-2x+6\ln|x+2|+C\right)=\frac{x^2+2}{x+2}$$

Your answers differ by a constant. Therefore, if one of them is correct, the other one is correct too.


Prove/refute property about a constrained sequence of numbers I need to prove or refute a property about a sequence of numbers.
Here is what is given to me:
Sequence ($a_1,a_2,...,a_k,a_{k+1},a_{k+2}$) containing $k+2$ numbers. Every number $0 < a_i \leq M, i=1,...,k+2$ for the same given constant $M$. Moreover, $\sum_{i=1}^{k+2} a_i = N$, for another given constant $N > 0$. The constants $N$ and $M$ are related by $kM \geq N, k > 1$.
Then, I need to prove or refute the following property: Can all consecutive pairs of numbers $a_i, a_{i+1}, i=1,...,k+1$ be defined such that $a_i + a_{i+1} > M$ ? Or does it lead to a violation of one of the given constraints?
I tried searching for something similar but in truth, I barely know what to search for. My tentative proofs do not really go anywhere meaningful, so I had to resort to more experienced math guys to help me with this. It has been a long time since I had to prove some property like this.

Assuming that given $k$, $N$ is selected such that
$$\sum_{i=1}^{k+2} a_i = N,$$
I claim it is possible $ \iff k\ge 3$
First of all we see the cases $k=1,2$ to check it is impossible:
(i) if $k=1$ then
$$M< a_1+a_2 < N \le kM = M;$$
(ii) if $k=2$ then we only have $(a_1,a_2,a_3,a_4)$, and
$$a_1+a_2>M \mbox{ and } a_3+a_4 >M ,$$
so
$$N = \sum_{i=1}^{k+2} a_i >M + M =2M = kM .$$
Now let $k\ge 3$: let $\epsilon > 0$ (arbitrarily small) and such that $\epsilon < M$, then I pick:
$$a_i= M \mbox{ if } i \mbox{ is even; } a_i = M -\epsilon \mbox{ if } i \mbox{ is odd.}$$
Now we obseve that $a_i + a_{i+1} = 2M - \epsilon > M$ anf that $0 < a_i \le M$, so they are good, then:
(i) if $k$ is even
$$\sum_{i=1}^{k+2} a_i = N = (2M -\epsilon)\Big(\frac{k}{2} + 1\Big) = (k+2)M - \epsilon\Big(\frac{k}{2}+1\Big)$$
which is possible if I pick $\epsilon$ such that
$$kM \ge (k+2)M - \epsilon\Big(\frac{k}{2}+1\Big)$$
which implies that
$$\epsilon \ge \frac{2M}{\frac{k}{2}+1} .$$
Also we have that $M> \epsilon$, so we can pick such a $\epsilon$ only if
$$M> \frac{2M}{\frac{k}{2}+1},$$
which means that $k > 2$.
(ii) if $k$ is odd
$$\sum_{i=1}^{k+2} a_i = N = (2M-\epsilon)\Big(\frac{k+1}{2}\Big) + a_{k+2} = (k+1)M - \epsilon \Big(\frac{k+1}{2}\Big) + a_{k+2} =$$
$$= (k+2)M - \epsilon \Big(\frac{k+1}{2} +1 \Big)$$
and here too we see it is possible if $\epsilon$ is such that
$$\epsilon \ge \frac{2M}{\frac{k+1}{2}+1} .$$
This implies that it is tue if
$$M > \frac{2M}{\frac{k+1}{2}+1},$$
which means if $k>1$.
This concludes my claim.

If $a_i+a_{i+1}>M$ for all applicable $i$, then
$$ N=\sum_{i=1}^{k+2}a_i=\frac{a_1}2+\sum_{i=1}^{k+1}\frac{a_i+a_{i+1}}2+\frac{a_{k+2}}2>\frac{k+1}2M$$
and in fact
$$ N=\sum_{i=1}^{k+2}a_i=\sum_{j=1}^{\frac{k+2}2}(a_{2j-1}+a_{2j})>\frac{k+2}2M\qquad\text{if $k$ is even}.$$
Hence we certainly need the additional condition that
$$\tag1 \left\lceil\frac{k+1}2\right\rceil M<N.$$
In particular, $kM\ge N$ contradicts $(1)$ when $k=1$ or $k=2$. Hence we incidentally also need
$$\tag2 k\ge3 $$
(but as said, $(1)$ implies $(2)$ in the given context).
Finally, we also need
$$ \tag3 M>0$$
to allow for $0<a_i\le M$ in the first place.

On the other hand, assume we have $k\in\Bbb N$, $N,M\in \Bbb R$ such that $(1)$ and $(3)$ and $kM\ge N$. Then we can let
$$a_i=\frac N{k+2}. $$
By $(1)$ and $(3)$ and $N\le kM$, this makes
$$ 0<a_i<M.$$
We clearly have
$$ \sum a_i = (k+2)\cdot \frac N{k+2}=N$$
and by $(1)$,
$$ a_i+a_{i+1}=\frac{2N}{k+2}\ge\frac N{\left\lceil \frac{k+1}2\right\rceil}>M,$$
as desired.


Factorizing a matrix into a matrix and its transpose Let $W\in \mathbb{R}^{n \times n}$ be a positive semi-definite matrix.

Then, what are some well-known factorization methods that guarantee $W=A^T A$, with the conditions being that

\begin{align}
1.& \ \ \ \ \ A \in \mathbb{R}^{n \times n}, \\
2.& \ \ \ \ \ \text{$A$ has the same rank as $W$}?
\end{align}

It's not possible to factor a general positive semidefinite matrix that way.

$A^TA$ is automatically symmetric. But there are positive semidefinite matrices that are not symmetric. Like $W=\begin{bmatrix}1&3\newline-1&1\end{bmatrix}$, which has $\vec{v}^tW\vec{v}=(v_1+v_2)^2\geq0$ for all $\vec{v}$.

Did you intend to ask about factoring a symmetric matrix? Or a Hermitian positive semidefinite matrix?

I don't know such a decomposition for all p.s.d. matrices $W$. But take a look at Matrix decomposition especially Cholesky decomposition.


Why should I believe that the real numbers model distances along a line? Taking the real numbers to be a complete ordered field, why do we believe that they model distances along a line? How do we know (or why do we believe) that any length that can be drawn is a real number multiple of some unit length?

Completeness often feels a bit technical at first: we show that there is exactly one complete ordered field up to isomorphism, but why should that confluence of properties correspond to line-ness?
I think it's more intuitive to focus instead on connectedness. This is really the same thing in our context, but is a priori phrased in more convenient language: the idea is that if I "cut" the line into a "lower piece" and an "upper piece," then there is some point which captures this cut. Specifically:

The line is connected, in the sense that it cannot be written as the disjoint union of two nonempty sets $A$ and $B$ where $A$ is downwards closed, $B$ is upwards closed, $A$ has no greatest element, and $B$ has no least element.

This is - for me at least - a pretty fundamental piece of the intuition I have about the line. (Connectedness is equivalent to completeness in our context, but is in my opinion more obviously a fundamental line property.) The fact that $\mathbb{R}$ is the unique connected ordered field then tells me that $\mathbb{R}$ is the only possible way we could faithfully "model" the line by a field, that is, the only way we could sensibly add/subtract/multiply/divide lengths.
This whole line of attack was developed by Dedekind in his Essays on the Theory of Numbers.

That said, we can critique this idea.
The line has three fundamental properties (to me anyways): it is a linear order without endpoints (duh), it is connected, and it is dense (= between any two elements is a third). These three properties are not enough to pin down a single linear order up to isomorphism: there are lots of connected dense linear orders without endpoints much larger than $(\mathbb{R};<)$. This does not contradict the above, since these "unreal" linear orders do not support a field structure.
So one way I could argue that the ordered field $(\mathbb{R};+,\times)$ does not faithfully model the intuitive line is if I gave up the assumption that lengths do in fact form a field! This raises a natural question:

What sort of algebraic structure can a connected dense linear order without endpoints other than $(\mathbb{R};<)$ support?

It turns out that the answer is very little: any two (nontrivial) connected ordered  groups are in fact isomorphic,$^*$ and in particular up to isomorphism the only (nontrivial) connected ordered group is $(\mathbb{R};+)$. So assuming we want to be able to add and subtract lengths in a reasonable way, we're stuck with $\mathbb{R}$.
This is pretty much case-closed for me: the idea of "non-additive intervals" is sort of a non-starter as far as my own intuition is concerned.

$^*$Here's a proof sketch:
Suppose $G$ is a nontrivial connected ordered group. First, note that by connectedness $G$ must be divisible: e.g. for each $x$ there must be some $y$ such that $y+y=x$, since otherwise we could partition $G$ into $\{y: y+y<x\}$ and $\{y: y+y>x\}$ contradicting connectedness.
Now - by nontriviality - fix some positive group element $g$. By divisibility we get an embedding $\eta$ of $(\mathbb{Q};+)$ into $G$ generated by sending $1$ to $g$. By connectedness, $ran(\eta)$ is cofinal in $G$ (otherwise look at the downwards closure of $ran(\eta)$); this gives us a homomorphism $h:G\rightarrow \mathbb{R}$ (think about sending $x\in G$ to the least upper bound in the sense of $\mathbb{R}$ of $\eta^{-1}(\{y: y<x\})$). And we can show that $h$ is a bijection - hence an isomorphism - by applying connectedness again.

I think steven gregory's answer is probably the best so far: we simply choose to believe that real numbers describe distances - it has turned out to be a useful notion, but it is simply a choice we made, it isn't absolute truth.
This really about the fundamental nature of mathematics: there are certain things we choose to accept as true witout proof (called axioms), and when we that maths represents absolute truth, it means simply that the logical statements of the form "if the axioms are true, then ..." are true.


Find the amount of natural numbers that can be written as $x^2$, $x^3$ and $x^5$ that are smaller or equal than $2^{30}$ Since I have not found any formula for this, I've written a quick Python script to calculate the number of numbers that can be expressed as $x^2$ that are $\le2^{30}$, just to see the result.

It took a little while to compute, and it returned $32769$. Wolframalpha says that $32769$ can be represented as $2^{15} + 1$, but I am still not seeing any pattern here.

EDIT: The script started from $0$, which explains the extra $+1$. The actual number of perfect squares that are $\le2^{30}$ is $2^{15} = 32768$.

Also, thanks to Eevee Trainer, I've been able to solve this more efficiently for $x^2$, $x^3$ and $x^5$ using their formula:

$\text{# of positive perfect k-th powers less than or equal to n} = \lfloor \sqrt[k] n \rfloor$

Therefore, these are the number of numbers that are less than or equal to $2^{30}$ for each of the following types:

perfect squares: $\sqrt[2] {2^{30}} = 2^{15}$
cubes: $\sqrt[3] {2^{30}} = 2^{10}$
powers of $5$: $\sqrt[5] {2^{30}} = 2^{6}$

I assume you want positive integers $x$; if it's just any kind of integer (positive or negative or 0), the below can be modified to apply. If it's just any real number, then the number is clearly infinite, but I imagine that's not at all the scope. So going forward, we'll be considering positive perfect squares less than some other number.

First, let's establish the underlying pattern. This will explain why the number of squares is coincidentally equal to $2^{15}+1 = \sqrt{2^{30}} + 1$.

This might be one of those kinds of cases where it's logical to try some small values first.

For example, let's find the number of positive perfect squares $s$ less than or equal to $n$.

Suppose $n=2^2$. Well, we have $s=1,4$. Suppose $n = 3^2$. Then $s=1,4,9$.

Keep trying further numbers, and it becomes clear: if $n$ is a perfect square, then

$$\text{# of positive perfect squares less than or equal to n} = \sqrt n$$

It should be easy to deduce that if $n$ is not a perfect square, it falls between two perfect squares, $\lfloor \sqrt n \rfloor ^2$ and $\lfloor \sqrt{n+1} \rfloor ^2$. But of course, there aren't going to be more perfect squares between the former and $n$, so we can just treat $n$ as the former. Then it can be deduced: for positive integers $n$,

$$\text{# of positive perfect squares less than or equal to n} = \lfloor \sqrt n \rfloor$$

Similar logic follows for the number of perfect cubes or perfect fifth powers or whatever:

$$\text{# of positive perfect k-th powers less than or equal to n} = \lfloor \sqrt[k] n \rfloor$$

(Note: This is by no means a formal argument, nor is meant to be. This is more a heuristic idea to show where the results you need come from.)

Take $n=2^{30} = (2^{15})^2$ to begin to get your solutions. So far, this only gets you $2^{15}$ solutions with respect to the number of squares (i.e. one off). This comes about on the assumption we have positive integer solutions (i.e. $x > 0$) and include the number we're searching at if it's a perfect square (i.e. $"..." \leq 2^{30}$).

The only conclusion I can think of is that $0^2$ is being counted as a further solution. It depends on the exact framing of the question whether that counts - whether you wanted natural number solutions, whether you wanted nonnegative integer solutions, positive integer solutions, etc., and of course to touch on the first whether the problem comes with the implicit assumption that $0$ is a natural number (this a contentious issue in mathematics).

So whether this solution is valid needs to be addressed to whomever gave you the problem.

As for why it might have popped up in your solution and why Wolfram gave the same answer, it depends on the code you used. If you started checking squares at $0$ and not $1$, then  that would explain it, but it depends on your specific implementation. Per a comment from you, it seems that you indeed included $0$ in your search so I figure that's why.

Only the squares up to $x=2^{15}$ satisfy the condition. Obviously there are $2^{15}+1$ of them.


Eigenvectors of a normal matrix According to the spectral theorem every normal matrix can be represented as the product of a unitary matrix $\mathbb{U}$ and a diagonal matrix $\mathbb{D}$
 $$\mathbb{A} = \mathbb{U}^H\mathbb{D}\mathbb{U}$$
meaning that every normal matrix is diagonalizable.
Does it necessarily mean that the unitary matrix has to be composed from the eigenvectors of $\mathbb{A}$ ?
I presume that not, because then the eigenvectors of every normal matrix would form an orthonormal set (rows and columns of a unitary matrix are orthonormal in $\mathbb{C}^n$). So am I right that only the set of eigenvectors of a hermitian (or symmetric while in $\mathbb{R}^n$) matrix is orthonormal?

An $n\times n$ matrix $A$ over the field $\mathbf{F}$ is diagonalizable if and only there is a basis of $\mathbf{F}^n$ of eigenvectors of $A$. This occurs if and only if there exists an invertible $n\times n$ matrix $Q$ such that $Q^{-1}AQ$ is a diagonal matrix; the column of $Q$ form the basis made up of eigenvectors, and conversely, if you take a basis made up of eigenvectors and arrange them as columns of a matrix, then the matrix is invertible and conjugating $A$ by that matrix will yield a diagonal matrix.

An $n\times n$ matrix $A$ with coefficients in $\mathbb{R}$ or $\mathbb{C}$ is orthogonally diagonalizable if and only if there is an orthonormal basis of eigenvectors of $A$ for $\mathbb{R}^n$ (or $\mathbb{C}^n$, respectively).

An $n\times n$ matrix with coefficients in $\mathbb{C}$ is orthogonally diagonalizable over $\mathbb{C}$ if and only if it is normal; a square matrix is orthogonally diagonalizable over $\mathbb{R}$ if and only if it is Hermitian. "Unitary" is usually reserved for complex matrices, with "orthogonal" being the corresponding term for real matrices.

Here is what I think is correct:
Normal matrices are matrices that have orthogonal eigenvectors.
Hermitian matrices are normal matrices that have real eigenvalues.

So this answers your first question in positive: Yes, the unitary matrix in your decomposition has the same eigenvectors as your original matrix.


Finding the antiderivative of $f(x)=\sqrt[3]{x^2+2x}$ $$f(x)=\sqrt[3]{x^2+2x}$$.
Let $g(x)$ be an antiderivative of $f(x)$. If $g(5)=7$, then what is the value of $g(1)$?
I tried doing integrating by parts repeatedly, but no success. Wolfram Alpha also gives something in a different type of function which I don't know.
Please help?

Which is the exact phrasing of the question? I mean, maybe you are not asked to compute but just to express the value in terms of $g$, i.e.:
$$g(1)=\int_5^1 \sqrt[3]{x^2+2 x} \, dx +7$$
because, at the end of the day, the definition of $g$ is simply:
$$g(x)=\int_5^x \sqrt[3]{t^2+2 t} \, dt +7$$


Definition of the nth derivative? [First post] If the definition of the derivative is
$$
f^\prime(x) = \lim_{\Delta x \to 0} \dfrac{f(x+\Delta x) - f(x)}{\Delta x}
$$
Would it make sense that the nth derivative would be (I know that the 'n' in delta x to the nth power is useless)
$$
f^{(n)}(x)=\lim_{\Delta x \to 0} \sum_{k=0}^{n}(-1)^k{n \choose k}\dfrac{f(x+\Delta x(n-k))}{\Delta x^n}
$$
I came to this conclusion using this method
$$
f^\prime(x) = \lim_{\Delta x \to 0} \dfrac{f(x+\Delta x) - f(x)}{\Delta x}
$$
(this is correct right?)
$$
f^{\prime\prime}(x) = \lim_{\Delta x \to 0} \dfrac{f^\prime(x+\Delta x) - f^\prime(x)}{\Delta x}=$$$$\lim_{\Delta x \to 0}\dfrac{\dfrac{f((x+\Delta x)+\Delta x)-f(x+\Delta x)}{\Delta x}-\dfrac{f(x+\Delta x)-f(x)}{\Delta x}}{\Delta x}=$$$$\lim_{\Delta x \to 0}\dfrac{f(x+2\Delta x)-2f(x+\Delta x)+f(x)}{\Delta x^2}
$$
After following this method a couple of times(I think I used it to the 5th derivative) I
noticed the pattern of
$$(a-b)^n$$
And that is how i arrived at
$$
f^{(n)}(x)=\lim_{\Delta x \to 0} \sum_{k=0}^{n}(-1)^k{n \choose k}\dfrac{f(x+\Delta x(n-k))}{\Delta x^n}
$$
Have I made a fatal error somewhere or does this definition actually follow through?
Thanks for your time I really appreciate it.
P.S. Any input on using tags will be appreciated.

This is probably not a good definition of the $n$th derivative.  To see this, consider the case  $n = 2$:
$$
f''(x) = \lim_{h \to 0}  \frac{f(x + 2h) - 2f(x + h) + f(x)}{h^2}
$$
Define $f: \mathbb{R} \to \mathbb{R}$ as follows.  First, define $f(0) = 0$.
Now define $f$ on the intervals $\left[-1, -\tfrac12\right)$ and $\left(\tfrac12, 1\right]$ to be your favorite unbounded function, for instance $\frac{1}{x^2 - 1/4}$ is a good choice.
Now, for any $x$, let $k$ be the unique integer such that $2^k x$ is contained in one of these intervals, and define $f(x) = 2^{-k} f(2^k x)$.

This construction satisfies $f(2h) = 2f(h)$ for all $h \in \mathbb{R}$, so the derivative formula above gives
$$
f''(0)
= \lim_{h \to 0} \frac{f(2h) - 2f(h) + f(0)}{h^2}
= \lim_{h \to 0} \frac{0}{h^2}
= 0
$$
However, $f$ is wildly discontinuous at $0$, and is in fact unbounded in any neighborhood containing $0$.

when you did for f''(x) you are taking both limits as a single limit for delta x. what I did is take $h_1$ for first limit and $h_2$ for second limit, so that nth derivative is limit $(h_1, h_2, h_3,.... h_n)$ --> $(0,0,0,....,0)$ and some function.


Determine which Fibonacci numbers are even (a) Determine which Fibonacci numbers are even. Use a form of mathematical induction to prove your conjecture.
(b) Determine which Fibonacci numbers are divisible by 3. Use a form of mathematical induction to prove your conjecture

I understand that for part a that all multiples of 3 of n are even. So F(0),F(3),F(6)... I just don't understand how to prove it.

For part B it is the same thing except multiples of 4

Please help, thank you!

Hint: You can look at the first few terms of the sequence modulo $n$, and then conclude a pattern (because each term is based upon the previous two). The first few terms of the Fibonacci sequence modulo $2$ are

$1,1,0,1,1,0,1,1,0,1,1,0,\ldots$

The first few terms of the Fibonacci sequence modulo $3$ are

$1,1,2,0,2,2,1,0,1,1,2,0,\ldots$

Now how can you formalize this argument using induction?

Another hint: you may want multiple base cases.

1,1,2,3,5,8 . . .
an even number and an odd number added together is odd, an odd number plus and odd number is even.


Find all $2 \times 2$ matrices $A$ such that $AB = BA$ for every $2 \times 2$ matrix $B$ Find all possible $2 \times 2$ matrices A that for any $2 \times 2$ matrix B,
AB = BA.

Hint: AB = BA must hold for all B. Try matrices B that have lots of zero entries.

I'm clueless as to how to solve this problem. How should I start it? I tried plugging in values for B that "have lots of zero entries" but didn't seem to see anything that could help.

Consider the following four matrices:

$$\left(\begin{array}{cc} 1 & 0 \\ 0 & 0\end{array}\right), \quad \left(\begin{array}{cc} 0 & 1 \\ 0 & 0\end{array}\right), \quad \left(\begin{array}{cc} 0 & 0 \\ 1 & 0\end{array}\right), \quad \left(\begin{array}{cc} 0 & 0 \\ 0 & 1\end{array}\right).$$

See what happens when you solve the equation $AB = BA$ for each of those four (let $B$ be each one of those four). To facilitate it, write $A = \left(\begin{array}{cc} a & b \\ c & d\end{array}\right)$. You will get a set of equations for the entries of $a$ which are easily solved. This trick is quite general.

Given a matrix B, consider any matrix that is a polynomial on $B$ with coefficients {$c_k$} in the field you are working with, i.e., take all $A$ with $$A=c_0I+c_1B+c_2B^2+...+c_nB^n$$. I actually think this gives you all such matrices $A$ , but I am not sure.


finding recursive formula and show it converges to a limit Suppose we are playing cards and we start with $1000$ dollars. Every hour we lose $\frac{1}{2}$ of our money and then we buy another $100$ dollars. I am trying to find $x_n$ for the amount of money the player has after $n$ hours.

I think we can just take $x_n = \frac{x_{n-1}}{2} + 100 $

An so, let $L = \lim x_n$. Then $L = \frac{L}{2} + 100 $ and so $L = 200$

Is this correct?

What you did is not wrong, but it's not complete.

What you did prove:

  If the sequence $x_n$ has a limit, then the limit is equal to $200$.

What you did not prove:

  The sequence $x_n$ has a limit.

Also, that's not what the question is asking you. The question says you need to find a formula for $x_n$, not the limit of $x_n$.


Example that $\lim \sup (x_n\cdot y_n)<\lim \sup (x_n)\cdot \lim \sup (y_n)$ This is a short question, I already managed to prove using definitions that $$\lim \sup (x_n\cdot y_n)\le \lim \sup (x_n)\cdot \lim \sup (y_n)$$

But I'm having trouble coming up with an example such that
$$\lim \sup (x_n\cdot y_n)<\lim \sup (x_n)\cdot \lim \sup (y_n)$$

I tried to consider alternative sequences but I'm not sure if I'm doing it right. I'm considering the following right now.
$$x_n=(1,0,1,0,...)$$
$$y_n=(0,1,0,1,...)$$
$$x_n\cdot y_n=(0,0,0,0,...)$$
$\lim \sup x_n \cdot y_n=0$ as there sequence is convergent.
But $\lim \sup x_n = 1$ and $\lim \sup y_n =1$ So it appears the inequality holds.
I just need a confirmation that what I'm doing is right. Sorry if this is a redundant question, I'm just learning this concept so it's a little fuzzy for me.

Note that $(x_n)$ and $(y_n)$ are non-negative.

Even values of x are zero, odd values are one.

y is the opposite.


How many distributions of $18$ different objects into $3$ different boxes. How many distributions of $18$ different objects into $3$ different boxes are there with twice as many objects in one box as in the other two combined$?$

Soln:

It appears to me as an arrangement problem with repetition of some sort.  As such I did this:  $$\binom{3}{1} \frac{18!}{(2n)! n! n! }$$

i did $\binom{3}{1}$ to account for the fact any of the $3$ boxes could get the double amount.  $\frac{18!}{(2n)! n! n! }$ was done partially because I have seen a formula relating to this sort of problem,  but personally I am trying to understand the REASON behind why this formula works here, that is if my treatment was correct

If you have $18$ items, the big box must have $12$ and the other two must have $6$ between them. There are $18 \choose 12$ ways to select the ones in the big box, $3$ ways to select the big box, now distribute the other $6$.

Out of $18$ we select any of the $12$ objects to be placed into any of the $3$ boxes.This can be done in $3*\binom{18}{12}$ ways.There remain $6$ distinct objects to be distributed into $2$ distinct boxes.This can be done in $64$ ways.    $P(6;0,6)+P(6;1,5)+P(6;2,4)+P(6;3,3)+P(6;4,2)+P(6;5,1)+P(6;6,0)=64...$