## Prove by induction that n2

How can I show that n2<n! for all n≥4 Step 1 For n=1, the LHS=42=16 and RHS=4!=24. So LHS< RHS. Step 2 Suppose the result be true for n=k i.e., k2<k! Step 3 For n=k+1 (k+1)2=k2+2k+1 What will be the next step? Answer If k!>k2 ⟹(k+1)!=(k+1)⋅k!>(k+1)k2 It is sufficient to show (k+1)k2≥(k+1)2⟺k2≥k+1 ⟺k(k−1)≥1 which is … Read more

## How can you prove that a function has no closed form integral?

In the past, I’ve come across statements along the lines of “function $f(x)$ has no closed form integral”, which I assume means that there is no combination of the operations: addition/subtraction multiplication/division raising to powers and roots trigonometric functions exponential functions logarithmic functions which when differentiated gives the function $f(x)$. I’ve heard this said about … Read more

## Number of permutations of $n$ elements where no number $i$ is in position $i$

I am trying to figure out how many permutations exist in a set where none of the numbers equal their own position in the set; for example, $3,1,5,2,4$ is an acceptable permutation where $3,1,2,4,5$ is not because 5 is in position 5. I know that the number of total permutations is $n!$. Is there a … Read more

## Prove 0! = 10! = 1 from first principles

How can I prove from first principles that 0! is equal to 1? Answer We need 0! to be defined as 1 so that many mathematical formulae work. For example we would like n! = n \times (n-1)! to work when n=1, ie 1! = 1 \times 0!. Also we require that the formula for … Read more

## Highest power of a prime pp dividing N!N!

How does one find the highest power of a prime p that divides N! and other related products? Related question: How many zeros are there at the end of N!? This is being done to reduce abstract duplicates. See Coping with *abstract* duplicate questions. and List of Generalizations of Common Questions for more details. Answer … Read more

## Units and Nilpotents

If ua=au, where u is a unit and a is a nilpotent, show that u+a is a unit. I’ve been working on this problem for an hour that I tried to construct an element x∈R such that x(u+a)=1=(u+a)x. After tried several elements and manipulated ua=au, I still couldn’t find any clue. Can anybody give me … Read more

## √c+√c+√c+⋯\sqrt{c+\sqrt{c+\sqrt{c+\cdots}}}, or the limit of the sequence xn+1=√c+xnx_{n+1} = \sqrt{c+x_n}

(Fitzpatrick Advanced Calculus 2e, Sec. 2.4 #12) For c>0, consider the quadratic equation x2−x−c=0,x>0. Define the sequence {xn} recursively by fixing |x1|<c and then, if n is an index for which xn has been defined, defining xn+1=√c+xn Prove that the sequence {xn} converges monotonically to the solution of the above equation. Note: The answers below … Read more

## How to solve linear recurrence relations with constant coefficients.

As questions regarding sequences that verifies a linear recurrence relation with constant coefficients are posted very often on this site and that there appear to be no reference post about it, so I decided to write one. I was also dissatisfied with pointing to the wikipedia or the brillant links to cite only the commonly … Read more

## Proving $n! > n^3$ for all $n > a$

Prove by induction: Find a, and prove the postulate by mathematical induction. $$\text{For all}~ n > a,~ n! > n^3$$ Where ! refers to factorial. So far I’ve done a bit of it, I’ll skip right to the inductive statement and assume that $k! > k^3$, then try to prove $(k+1)! > (k+1)^3$ Inductive statement: … Read more

## Alternate ways to prove that $4$ divides $5^n-1$

I was working for various method to solve this: For all $n\in \mathbb N$: $4\;\mid\;(5^{n}-1)$. My try was: 1st: $$n=1 \to 4|5^1-1\\n \geq 2 \to 5^n=25,125,625,3125,…\\ n\geq 2 \to 5^n=\overline{…a_4a_3a_225}\\=5+2(10)=100a_2+1000a_3+10^4a_4+…=\\25+100(a_2+10a_3+…)=25+100q\\{\color{Red}{5^n-1=25+100q-1=24+100q=4(6+25q)} }$$ 2nd: divide into cases (even,odd) $$n=2k \to 5^n-1=5^{2k}-1=\overset{even}{(5^k-1)}\overset{even}{(5^k+1)}=\\2q*2q’=4qq’ \to {\color{Blue} {4|5^{2k}-1}} \\n=2k+1 \to 5^n-1=5^{2k+1}-1 =5^{2k+1}-(5)+4\\=5*5^{2k}-5+4=5(5^{2k-1}-1)+4\\ \overset{{\color{Blue} {4|5^{2k}-1}}}{\rightarrow} =5(4qq’)+4 =4q”$$ 3rd: induction $$p_1:4|5^k-1\\p_k:4|5^k-1\\p_{k+1}:4|5^{k+1}-1\\$$ multiply R.H.S … Read more