# Tag Info

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 HINT$((n+1)^3-(n+1))-((n^3)-(n))=3n+3n^2$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

Here is a simple counterexample: a <=====> b ----> c

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^kin 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$\$ ...

Top 50 recent answers are included