New answers tagged

2

You can look at how much space a square takes. I do not mean the area of the square. For example, with $n = 2$ the diagonal square and the $2 \times 2$ square both take $2 \times 2$ space. If a square takes $k \times k$ space, then you can place it at $(n+1-k)^2$ different positions. Now how many squares take $k \times k$ space? The answer is $k$. You can ...


0

Once you have your formula, the proof is straightforward. If $f(x) = \sum_{k=0}^{\infty}\frac{x^{2k}}{k!} $, then $\begin{array}\\ f'(x) &= \sum_{k=0}^{\infty}\frac{2kx^{2k-1}}{k!}\\ &= \sum_{k=1}^{\infty}\frac{2kx^{2k-1}}{k!} \qquad\text{since the }k=0\text{ term is zero}\\ &= \sum_{k=1}^{\infty}\frac{2x^{2k-1}}{(k-1)!} ...


0

Note: This proof relies on a formula for the $n^{th}$ derivative of $f(x)$ that can be found HERE The proof is rather extensive, and would roughly quadruple the length of this answer. Proof of The Taylor Expansion of $f(x)$ $$\mbox{Prove true that } \ 1 + x^2 + \frac{x^4}{4} + \frac{x^6}{6} + \cdots + ...


2

Let $a_n = \dfrac{1*4* .. *(3n - 2)}{2*5 .. *(3n - 1)}$. The sequence converges from the Monotonic Convergence Theorem, as it is bounded below (by zero) and is decreasing: $a_{n + 1} = a_n\dfrac{3n + 1}{3n + 2} < a_n$


1

$$u_n>\frac{3n-2}{3n-1}u_n=u_{n+1}$$ and so by induction the entire sequence is monotonic decreasing.


1

Your identity is a simple consequence of the multinomial theorem. For $x=(x_1,\ldots,x_n)$ and $\alpha=(\alpha_1,\ldots,\alpha_m)\in\mathbb{N}^m$ we write $x^\alpha:=x_1^{\alpha_1}\cdots x_m^{\alpha_m}$ (and, as you do, $|\alpha|:=\alpha_1+\cdots+\alpha_m$, $\alpha!:=\alpha_1!\cdots\alpha_m!$). Then \begin{equation*} (x_1+\cdots+x_m)^r \,=\, ...


2

Seems like an induction on $m$. Suppose the result holds for $\Bbb N^m$. For $\alpha\in\Bbb N^{m+1}$write $$\alpha=(\alpha',\beta),$$where $\alpha'\in\Bbb N^m$ and $\beta\in\Bbb N$. Then $$\sum_{\alpha\in\Bbb N^{m+1},|\alpha|=r}\frac{1}{\alpha!} =\sum_{\beta=0}^r\frac1{\beta!}\sum_{\alpha'\in\Bbb N^m,|\alpha'|=r-\beta} ...


0

No. Suppose some proposition $P(n)$ is true for all integer $n \ge 1$. Take any integer $a$. Then the proposition $Q(n) := P(n-a)$ is true for all integer $n \ge a + 1$. A proof by induction for $Q(n)$ would begin with base case $n = a + 1$, which is not necessarily $1$.


0

Absolutely not. You prove that a(n) implies a(n+1) for n >= N. Then you prove a(n) for 1 <= n <= N. N can be large. I think I heard of practical cases where N >= 10^16.


1

Think of the following: Suppose you want to prove for appropriate $n$ that $2^n>n^2$. Would the induction base be to verify for $n=1$? Try that and see what happens.


4

Integrate both sides from $0$ to $x$ and add $1$.


0

Well, first off you need $x >0$, not just $ x \geq 0$. So, you know $e^x = \sum_{n=0}^{\infty} \frac{x^n}{n!}$, which is, by definition, $\lim_\limits {k \to \infty} \sum_{n=0}^k\frac{x^n}{n!}$. Let $a_n = \frac{x^n}{n!}$, and $b_k = \sum_{n=0}^k\frac{x^n}{n!} = \sum_{n=0}^k a_n$. Clearly, $a_n > 0$, since $x>0$. Moreover, $b_{k+1} = b_k + a_{k+1} ...


0

I would use Taylor theorem with the Mean-value forms of the remainder, it is straightforward You can check https://en.wikipedia.org/wiki/Taylor%27s_theorem


0

I think you should have done it like this By assumption: k+1<2^k 2(k+1)<2*2^k * by 2 both sides since 2*2^k>2(k+1) and 2(k+1)>k+1 for example if n>10 therefore n>5 Therefore k+1<2*2^k =2^(k+1) LHS < RHS Then statement n<2^n is valid for all Natural Numbers ...


3

A well known way of generating a sequence of $n$ consecutive numbers that aren't prime is to consider $(n+1)!+2, (n+1)!+3,\ldots, (n+1)!+n$ - it's quite obvious that each of these numbers are divisible by $2, 3,\ldots, n$. We could perform that for $n=65$, the generated sequencemust contain five consecutive elements of your sequence, thus producing a ...


2

Consider the system of congruences $$13x\equiv -11\pmod{2}, \quad13(x+1)\equiv -11\pmod{3},\quad 13(x+2)\equiv -11\pmod{5},\quad 13(x+3)\equiv -11\pmod{7},\quad 13(x+4)\equiv -11\pmod{11}.$$ By the Chinese Remainder Theorem, this has infinitely many solutions. So there are infinitely many consecutive $5$-tuples of our sequence which are respectively ...


2

No, because the density of primes in this, and any other, arithmetic progression is 0. See https://en.wikipedia.org/wiki/Dirichlet's_theorem_on_arithmetic_progressions for details.


-1

We want to prove that when n is an integer, $n^3-n$ is divisible by 3. To make things easier, we can simply prove the following: $$(\lfloor n \rfloor ^3 - \lfloor n \rfloor) mod (3)=0$$ Using the formula relating floor to modulo: $$\lfloor n \rfloor^3 - \lfloor n \rfloor - 3*\lfloor \frac {\lfloor n \rfloor^3 - \lfloor n \rfloor} 3 \rfloor = 0$$ What we ...


1

In the inductive step we assumed that $k^3 - k$ is divisible by 3 which means that $k^3 - k = 3M$ where $M$ is an integer. Now we can easily deduce $P(k) \rightarrow P(k+1)$. \begin{align} (k + 1)^3 - (k + 1) &= k^3 +3k^2 +3 + 1 -k - 1\\ &= (k^3- k) + 3k^2 + 3\\ &= 3M +3k^2 + 3\\ &= 3(M + k^2 + 1)\\ &= 3Z \end{align} where $Z = M + k^2 ...


0

We get $k^3+3k^2+2k=k(k+1)(k+2)$ because k is an integer and we have a multiplications of 3 sequential integers it is divisible by 3. Note this does not use induction.


0


1

Without induction and completely elementary: $n! = \prod_{k=1}^n k $ so $\begin{array}\\ n!^2 &= (\prod_{k=1}^n k)^2\\ &= (\prod_{k=1}^n k)(\prod_{k=1}^n k)\\ &= (\prod_{k=1}^n k)(\prod_{k=1}^n (n+1-k))\\ &= \prod_{k=1}^n k(n+1-k)\\ &= \prod_{k=1}^n (k(n+1)-k^2)\\ &= \prod_{k=1}^n ...


1

It's worth noting that some induction proofs are more cleanly presented if you use $n-1$ for the inductive hypothesis. That is, let's assume we have $(n-1)!\lt\left(n\over2\right)^{n-1}$. Then $$n!=n(n-1)!\lt n\left(n\over2\right)^{n-1}=2\left(n\over2\right)^n$$ and hence it suffices to show that $$2\le\left(n+1\over n\right)^n=\left(1+{1\over ...


1

A full derivation. Stop here if you only are looking for a hint. Assume $$ n! < \left(\frac{n+1}{2}\right)^n $$ holds for some $n\geq 2$. Then, $$ (n+1)! = (n+1)n! < (n+1)\left(\frac{n+1}{2}\right)^n $$ by the induction hypothesis. Now, it remains to conclude to show that $$ (n+1)\left(\frac{n+1}{2}\right)^n \leq \left(\frac{n+2}{2}\right)^{n+1} $$ ...


1

$$ \frac{ \left( \frac{n+1}{2} \right)^n}{\left( \frac{n}{2} \right)^{n-1}} \; \; = \; \; \frac{1}{2} \; n \; \left(1 + \frac{1}{n} \right)^n $$


4

By hypothesis, we have $$\begin{align} (n+1)!&=(n+1)n!\\\\ &<(n+1)\left(\frac{n+1}{2}\right)^n\\\\ &=2\left(\frac{n+1}{2}\right)^{n+1}\end{align}$$ From Bernoulli's Inequality, we find that $$\begin{align} \left(\frac{n+2}{2}\right)^{n+1} &=\left(\frac{n+1}{2}\right)^{n+1}\left(1+\frac{1}{n+1}\right)^{n+1}\\\\ &\ge ...


0

Check that after $6$ steps we’re in state $3$, and the tape has $\ldots 0\color{red}{1}110\ldots\;$, where the red cell is the current location of the read/write head. Check that after another $4$ steps we’re in state $0$, and the tape has $\ldots 01110\color{red}{0}0\ldots\;$. Then check that the next $6$ steps proceed just like the first $6$, and we end up ...


2

Pick two vertices $u,v$ in $G$. If there is an edge $uv$ you are done. Otherwise, $u$ is connected to at least $\frac{n}{2}$ of the remaining $n-2$ vertices. Same way $v$ is connected to at least $\frac{n}{2}$ of the remaining $n-2$ vertices. By the pigeon hole principle, $u$ and $v$ must be connected to a common vertex $w$. P.S. This shows something ...


3

Hardmath's answer gives the correct proof, but I wanted to also answer your first question and point out the problems with the proofs you posted. "At least $\frac{n}{2}$" means "$\geq \frac{n}{2}$," so if $\frac{n}{2}$ is not an integer, you know the degree of each vertex is actually greater than $\frac{n}{2}$ (i.e., round up, not down). There's a problem ...


2

Suppose $G$ is not connected and has $n$ vertices. Some component of $G$ then has at most $n/2$ vertices. A vertex in this component then has degree at most one less, i.e. $\lt n/2$. To make this a "proof by contradiction" we need only begin with assuming $G$ has degrees at least $n/2$ for every vertex.


1

Here is the main part of the inductive step: \begin{align} \sum_{i=0}^{k+1}(i+1)&= \sum_{i=0}^k(i+1)+(k+2)\tag{by definition}\\[1em] &= \frac{(k+1)(k+2)}{2}+(k+2)\tag{by inductive hyp.}\\[1em] &= \frac{(k+1)(k+2)+2(k+2)}{2}\tag{common denom.}\\[1em] &= \frac{(k+2)(k+1+2)}{2}\tag{factor out $(k+2)$}\\[1em] &= ...


1

So how induction works is that we first need to prove our base case. In this problem the base case is $n=1$. The $n=1$ base case yields $\sum_{j=o}^1 (j+1) = (0+1)+(1+1) = 3 = \frac{(1+1)(1+2)}{2}$. So this proves the base case since the answer to $\sum_{j=o}^1 (j+1)$ is of the form $\frac{(n+1)(n+2)}{2}$. We now make our assumption (the inductive ...


0

There are two mistakes here. Mistake 1) To prove all members of some given set $A$ have some property, it is not valid to argue by induction on the number of elements of $A$: "By induction on the number of (all) algorithms ..." is not a valid method of proof. Mistake 2) The induction scheme in the proposed proof is valid if what we were trying to prove is: ...


1

Derived this solution but just realised that it is a bit similar to the one posted by G Cab above, but here it is anyway. $$\begin{align} \sum_{i=0}^n \color{blue}{2^i}\binom{2n-i}n &=\sum_{i=0}^n\color{blue}{\sum_{j=0}^i\binom ij}\binom {2n-i}n\\ &=\sum_{j=0}^n\sum_{i=j}^n\binom i{i-j}\binom{2n-i}{n-i} &&\text{swapping indices and using ...


2

Multiply by $4$ and look at things mod $5$: $$4(2^{2^n-2}+1)=2^{2^n}+4=2^{4\cdot2^{n-2}}+4\equiv1+4\equiv0\mod5$$ so $5$ is a prime divisor of $2^{2^n-2}+1$. Note that for $n=2$, $2^{2^2-2}+1=5$, but for $n\ge3$, $2^{2^n-2}+1\gt5$, so $5$ is a proper divisor.


2

$2^n+1$ can only be prime, if $n$ is a power of $2$. If $p$ is an odd prime factor of $n$, $2^\frac{n}{p}+1$ is a proper divisor of $2^n+1$. It is clear that $2^n-2$ hast at least $1$ odd prime factor for $n\ge 3$.


5

Induction isn’t needed. All you need is the fact that $a+b\mid a^n+b^n$ for odd positive integers $n$. Observe that $$2^{2^n-2}+1=4^{2^{n-1}-1}+1=4^{2^{n-1}-1}+1^{2^{n-1}-1}\;.$$ $2^{n-1}-1$ is odd for $n\ge 2$, so $4+1=5$ divides the sum of odd powers, and for $n\ge 3$ the expression is greater than $5$.


4

You can just try to calculate it directly: For $\alpha\geq 1$, we need to try the definition (analytical extension) of $\sum_{k=1}^\alpha\frac{1}{k}$ "appear" in the definition of $\sum_{k=1}^{\alpha+1}\frac{1}{k}$: \begin{align*} ...


0

Pierre de Fermat called it "infinite descent". The natural numbers are well-ordered, which is short for saying that if there is a natural number with property $P$, there is a LEAST one with property P. So suppose $\neg A_n$ means "$n$ has property $P.$" So if $\neg A_n$ is true for any $n$, then there is a least $k$ such that $\neg A_k.$ But if $A_1$ is ...


0

As others have noted, you’ve somewhat misunderstood the mechanics of a proof by induction. Say that we want to use induction to prove that some statement $P(n)$ about integers $n$ is true for all positive integers. We verify that $P(1)$ is true. We then prove that if $P(n)$ is true for some (unspecified) $n$, then $P(n+1)$ must necessarily be true. At ...


1

Hint: \begin{align} \sum_{k=0}^{2n+2}\frac{(-1)^k}{k!(2n+2-k)!} =\frac{1}{(2n+2)!}\sum_{k=0}^{2n+2}(-1)^k{2n+2\choose k} =\frac{1}{(2n+2)!}(1-1)^{2n+2}=0. \end{align}


1

Both $a_n$ and $b_{n}$ are given by convolutions: $$\begin{array}{cclcl} a_n &=& \displaystyle\sum_{a+b=n}\frac{1}{(2a+1)!}\cdot\frac{1}{(2b+1)!} &=& \displaystyle[x^n]\left(\sum_{c\geq 0}\frac{x^c}{(2c+1)!}\right)^2 \\ b_n &=& \displaystyle\sum_{a+b=n}\frac{1}{(2a)!}\cdot\frac{1}{(2b)!} &=& ...


1

You may have misunderstood parts of the concept. One part of induction is: You prove If $A_n$ holds, then $A_{n+1}$ holds as well. And yo prove this implication for all values (as natural number) of $n$. So in effect you do not only prove that $A_{17}$ implies $A_{18}$, but all at once also that $A_{42}$ implies $A_{43}$ and that $A_{1729}$ implies ...


0

You also have to prove that it is true for some specific value of $n$. The idea is that given "$A_1$ is true" and "if any $A_n$ is true, then also $A_{n+1}$ must be true", you can conclude that every $A_n$ is true, i.e., each of $A_1,A_2, A_3,A_4,\cdots$ must be true. It's a sort of bootstrap procedure. You combine the hypotheses to conclude $A_2$ from ...


0

Suppose you have a statement $P(n)$, that says something about or involving the natural number $n$. The job of a mathematical induction proof is to show that $P(n)$ is true for all natural numbers. The way such a proof works is as follows. Step 1: the base case. One must prove that $P(1)$ is true. Step 2: the inductive case. One assumes that $P(k)$ holds ...


0

Your explanation is a bit mixed up: we assume $A_n$ and derive $A_{n+!}$, but by itself this is not enough to deduce either $A_n$ or $A_{n+1}$. What you're missing is that we need to prove $A_n \Rightarrow A_{n+1}$ for all $n$. Suppose I want to show that the number $5$ is bigger than $1$. Since $5 = 4+1$ is bigger than $4$, we'd be done if we could show $4 ...


0

This is a duplicate of other threads on the topic on induction. However I will give you a short summary/intuitive answer: The base case is important. We first show that $A_0$ hold, then assume that $A_n$ hold and show that this implies that $A_{n+1}$ hold. Thus, since $n$ is any number, we may say $n=0$. We know that $A_n=A_0$ hold, but if $A_n$ hold, we ...


0

Here is a variant using the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$ in a series. We can write this way \begin{align*} [z^k](1+z)^n=\binom{n}{k} \end{align*} We obtain \begin{align*} \sum_{k=0}^{n}2^k\binom{2n-k}{n}&=\sum_{k=0}^{n}2^k\binom{2n-k}{n-k}\tag{1}\\ &=\sum_{k=0}^\infty2^k[z^{n-k}](1+z)^{2n-k}\tag{2}\\ ...


1

Combinatorial proof: we'll write $[n]$ for $\{1,2,\dots, n\}$, and $[n]^{(r)}$ for the collection of all $r$-sized subsets of $[n]$. We use the standard $[i, j]$ for $\{i, i+1, \dots, j \}$. We exhibit a bijection between $$\{ (i, s \subseteq [i], t \subseteq [i+1, 2n]^{(n-i)}) : i = 0, 1, \dots, n \}$$ and the subsets of $[2n]$. Let $$\begin{equation} ...



Top 50 recent answers are included