Tag Info

New answers tagged

2

This isn't quite what you're looking for, but it may be interesting to you and was too long to put in a comment. Rather than by an explicit series, it's also possible to define $y(x) = e^x$ as the unique solution (say, defined on the real line) of $y = y'$ with $y(0) = 1$. For any $a$, the function $y_a(x) = \frac{1}{y(a)}\, y(x + a)$ then also clearly ...


3

Hint: $$\sum_{n=0}^{\infty}\frac{1}{n!}x^n\cdot\sum_{m=0}^{\infty}\frac{(-1)^m}{m!}x^m = \sum_{k=0}^\infty c_k x^k$$ where $$c_k = \sum_{n+m=k}\frac{1}{n!}\frac{(-1)^{m}}{m!} = \frac{(-1)^k}{k!}\sum_{n=0}^{k}{k\choose n}(-1)^{n}$$ The last sum can be evaluated using the Binomial formula.


0

For the base case simply show that the premise is true for the smallest positive integer: $\mathsf P(1)$. For the iterative case, you have to show that if the premise holds for $n$, then it is implied to hold for $n+1$.   $\mathsf P(n)\implies\mathsf P(n+1)$ Do that by substituting $n+1$ for $n$ and demonstrate that the left and right hand side both ...


0

For n+1 it is $1+3+3^2+\ldots+3^{n-1}+3^n=\frac{3^{n+1}-1}{2}$ $\left( 1+3+3^2+\ldots +3^{n-1}\right) +3^n=\frac{3\cdot 3^{n}-1}{2}$ $\left( 1+3+3^2+\ldots +3^{n-1}\right) +3^n=\frac{(1+2)\cdot 3^{n}-1}{2}$ $\left( 1+3+3^2+\ldots +3^{n-1}\right) +3^n=\frac{1\cdot 3^{n}-1}{2}+\frac{2\cdot 3^{n}}{2}$ $\left( 1+3+3^2+\ldots +3^{n-1}\right) +3^n=\left( ...


2

Suppose that $x \neq 1$. We wish to show by inducting on $n$ that $\sum\limits_{k=0}^{n-1}x^{k} = \frac{x^{n} - 1}{x-1}$. Then $1 = \frac{x-1}{x-1}$ so that the formula holds for $n = 1$. Suppose that we have $\sum\limits_{k=0}^{n-1}x^{k} = \frac{x^{n} - 1}{x-1}$. We must show that $\sum\limits_{k=0}^{n}x^{k} = \frac{x^{n+1} - 1}{x-1}$. We have ...


5

Show $3^{1-1}=\dfrac{3^1-1}{2}$ Assume $\sum\limits_{k=0}^{n-1}3^k=\dfrac{3^n-1}{2}$ Prove $\sum\limits_{k=0}^{n}3^k=\dfrac{3^{n+1}-1}{2}$: $\sum\limits_{k=0}^{n}3^k=(\sum\limits_{k=0}^{n-1}3^k)+3^n$ $(\sum\limits_{k=0}^{n-1}3^k)+3^n=\dfrac{3^n-1}{2}+3^n$ $\dfrac{3^n-1}{2}+3^n=\dfrac{3^n-1+2\cdot3^n}{2}$ ...


2

To make sure consider $u=\frac{1}{x}$. Then 1st limit $$\lim\limits_{u\to \infty} \frac{e^{-u^2}}{u^{n}} \quad \forall n \in \mathbb{N}$$ Using many well-known methods ($\varepsilon-\delta$, for example) you can prove that it is $0$. For better understanding it means that exponential decays faster than any power function. The second is a corollary from the ...


1

The statement $$\sum_{k=0}^{n}|\cos(k)| \geq \frac{n}{2}$$ appears to be true, but it is not in general true that $$\frac{n}{2} + |\cos(n+1)| \geq \frac{n+1}{2}$$ (e.g., this is false for $n=1$). So I don't think it will be useful to decompose the sum as $$\sum_{k=0}^{n+1} |\cos(k)| = |\cos(n+1)| + \sum_{k=0}^n |\cos(k)|$$ because we don't have a lower bound ...


0

Usually in Induction we do the following: Show that the relation is true for the case $k=1$,i.e.prove that $\mathfrak{R}(1)$ is true, usually by putting values. Assume truth of the relation for a general value of $k$,i.e. assume $\mathfrak{R}(k)$ is true. Show that by assuming truth for a value of $k$ proves that the relation is also true for $(k+1)$, ...


0

Here's what I would do: $$ f(k) = k^2 - 4 \implies f(k+1) = (k+1)^2 - 4 = k^2 + 2k - 3, $$ so $f(k+1)=f(k) + 2k + 1$.


1

In terms of strategies to find a formula, if you have no idea your best bet might to start computing. Let's compute the first few sums... $$1 + 1!1=2$$ $$1+1!1+2!2 = 2+2!2=2(1+2!)=2\cdot 3$$ $$1+1!1+2!2+3!3= 6+3!3=2\cdot 3 \cdot (1+3)=2\cdot 3 \cdot 4$$ $$1+1!1+2!2+3!3+4!4 = 24+4!4=2\cdot 3 \cdot 4 (1+4)= 2\cdot 3 \cdot 4 \cdot 5$$ $$\vdots $$ Do you ...


4

Hint: Let $f(n) = 1 + \displaystyle\sum_{j = 1}^{n}j \cdot j!$. Then, we have $f(0) = 1$ and: $f(n+1)-f(n) = \left[1 + \displaystyle\sum_{j = 1}^{n+1}j \cdot j!\right] - \left[1 + \displaystyle\sum_{j = 1}^{n}j \cdot j!\right] = (n+1) \cdot (n+1)!$ $= (n+2) \cdot (n+1)! - 1 \cdot (n+1)! = (n+2)! - (n+1)!$. Can you think of a function which satisfies ...


0

You might find parts of the following book chapter helpful: B. Jacobs and J.J.M.M. Rutten. An introduction to (co)algebras and (co)induction. In: Advanced topics in bisimulation and coinduction, pp. 38-99, 2011. Best, Jan


1

I think it is easier to prove the claim directly without auxiliary lemma. Denote $B:=\{x\in A; p(x)\}$. If we assume that $A\setminus B$ is non-empty, then there exists the smallest element $m:=\min(A\setminus B)$. What can you say about $m$? Can you get a contradiction from this? If you (or the authors of the book) insist on using the lemma stated in ...


0

If you are trying to prove the statement: If $S = \{ k, k + 1, k + 2, \cdots \}$ for some integer $k$, and $T \subseteq S$ with $k \in T$ and the property that if $n \in T \implies n + 1 \in T$, then prove $T = S$. Here is the proof: To show $T = S$, we need to show $T \subseteq S$ and $S \subseteq T$. First, let's show $T \subseteq S$. By definition, ...


2

$ 1! + 2! + \cdots + n! \le n! + n! + \cdots + n! = n\cdot n! < (n+1)\cdot n! = (n + 1)! $


2

Satisfy yourself with the first few values that: \begin{align} T(2^k)&=2T(2^{k-1})+2^k\\ &=4T(2^{k-2})+2^k+2^k\\ &=8T(2^{k-3})+3\cdot2^k\\ &\vdots\\ &=2^{k-1}T(2^1)+(k-1)\cdot2^k\\ &=2^k+(k-1)\cdot 2^k\\ &=k\cdot2^k \end{align} So if we say $2^k=n$ then $T(n)=\log_2(n)\cdot n$


0

For small values of $n$, we have $T(2),T(4),T(8),T(16),\ldots=2,8,24,64\ldots$ Can you find a connection between $n$ and $T(n)$? Let $n=2^k$, and use induction on $k$. So $U(k)=T(2^k)$, and $U(k+1)=2U(k)+2^k$.


1

$$a\left(n+1\right)<a\left(n\right)\iff n\left(2^{n+1}-1\right)<\left(n+1\right)\left(2^{n+1}-2\right)\iff n+2<2^{n+1}$$


1

\begin{align} a(n+1)&=\frac{1}{(n+1)(1-(1/2)^{n+1})} \\ &<\frac{1}{n(1-(1/2)^{n+1})} \\ &=\frac{1}{n(1-(1/2)^{n})+n(1/2)^n/2} \\ &<\frac{1}{n(1-(1/2)^n)}=a(n) \end{align}


0

$$ a(n) - a(n+1) = \frac{1}{n} \biggl( \biggl(1 - \frac{1}{2^n} \biggr) - \biggl( 1 - \frac{1}{n+1} \biggr) \biggl( 1 - \frac{1}{2^{n+1}} \biggr) \biggr) = \frac{1}{n} \biggl( \frac{1}{n+1}\biggl( 1 - \frac{1}{2^{n+1}} \biggr) - \frac{1}{2^{n+1} } \biggr) = \frac{2^{n+1} - (n+2)}{2^{n+1}n(n+1)} > 0 $$


3

Assume that $n$ is a power of $2$ so that $n = 2^k$ for some $k \in \mathbb N$. Then by unrolling the recursion, observe that: \begin{align*} T(n) &= T(2^k) \\ &= 2 \cdot T(2^{k-1}) \\ &= 2^2 \cdot T(2^{k-2}) \\ &= 2^3 \cdot T(2^{k-3}) \\ &= \cdots \\ &= 2^{k-2} \cdot T(2^{2}) \\ &= 2^{k-1} \cdot T(2) \\ &= 2^{k-1} \cdot 2 \\ ...


0

$$1! + 2! + .... + n! < (n + 1)!\Rightarrow$$ $$1! + 2! + .... + n!+(n + 1)! < (n + 1)!+(n + 1)!=$$ $$=2(n + 1)!<(n+2)(n + 1)!=(n + 2)!$$


8

You have all the right pieces, but it's pretty sloppy. Here's a cleaned up version. We will prove by induction on $n \in \mathbb N$ that: $$ 1! + 2! + \cdots + n! < (n + 1)! \tag{$\star$} $$ Base Case: Notice that $(\star)$ holds for $n = 1$, since: $$ 1! = 1 < 2 = (1 + 1)! $$ Inductive Step: Assume that $(\star)$ holds for $n = k \geq 1$. It ...


2

Hint $\ $ By induction $\,\alpha^n,\,\bar\alpha^{\,n} = j \pm k\sqrt{5}\,$ are $\,\color{#c00}{\rm conjugate}\,$ (so their sum $= 2j\in\Bbb Z)$ The inductive step is: $\,\ \overline{\alpha^{n+1}} =\, \color{#0a0}{\overline{\alpha\,\alpha^n} =\,\bar\alpha}\,\color{#c00}{\overline{\alpha^n}}\,\overset{\color{#c00}{\rm ...


3

The statement we are to prove is not that we can partition the triangle into $2n + 1$ triangles using the $n + 3$ points as described. Rather, it says that if we do partition the triangle using the $n + 3$ points as described, the result will always be $2n + 1$ triangles. The argument fails because there are partitions of the triangle that can be done using ...


9

From the theory of sequences defined by a linear recurrence relation with constant coefficients, the sequence $u_n$ satisfies $u_{n+2}=6u_{n+1}-4u_n$ and $u_0=2$ and $u_1=6$. Then, if you assume that $u_n$ and $u_{n+1}$ are integers, it follows immediately that $u_{n+2}$ is also an integer. You can write a strong induction from this to have a complete ...


3

If $n$ is odd then for all reals $x, y$ we have $$(x+y)^{n} + (x-y)^{n} = 2x^n + 2\sum_{j\ \text{odd}}\binom{n}{j}x^{j}y^{n-j};$$ if $n$ is even then for all reals $x, y$ we have $$(x+y)^{n} + (x-y)^{n} = 2x^n + 2y^n + 2\sum_{j\ \text{even}}\binom{n}{j}x^{j}y^{n-j}.$$ Putting $x := 3$ and $y := \sqrt{5}$ finishes the proof, for the irrational terms are all ...


4

Let $v_n = (3+\sqrt{5})^n - (3-\sqrt{5})^n$, then $$ u_1 = 6, v_1 = 2\sqrt{5} $$ And $$ u_{n+1} = (3+\sqrt{5})(3+\sqrt{5})^n + (3-\sqrt{5})(3-\sqrt{5})^n = 6u_n + \sqrt{5}v_n $$ $$ v_{n+1} = (3+\sqrt{5})(3+\sqrt{5})^n - (3-\sqrt{5})(3-\sqrt{5})^n = 6v_n +\sqrt{5}u_n $$ If $v_n$ is an integer multiple of $\sqrt{5}$ and $u_n$ is an integer, then $v_{n+1}$ is ...


10

Outline: For the (strong) induction step, we can use the fact that $$(3+\sqrt{5})^{n+1}+(3-\sqrt{5})^{n+1}=\left[(3+\sqrt{5})^{n}+(3-\sqrt{5})^{n}\right]\left[(3+\sqrt{5})+(3-\sqrt{5})\right]-(3+\sqrt{5})(3-\sqrt{5})\left[(3+\sqrt{5})^{n-1}+(3-\sqrt{5})^{n-1}\right].$$ Note that $(3+\sqrt{5})+(3-\sqrt{5})$ and $(3+\sqrt{5})(3-\sqrt{5})$ are integers. ...


1

As you said each strip $S_k$ has (11-k)(2k-1) tiles. You are being asked to find the total number of tiles on the 10 strips which should be: $\sum_{k=1}^{10} S_k = \sum_{k=1}^{10} (11-k)(2k-1)$ $\quad\quad\quad\quad = \sum_{k=1}^{10} 23k-2k^2-11$ $\quad\quad\quad\quad = 23\sum_{k=1}^{10} k-2\sum_{k=1}^{10}k^2-\sum_{k=1}^{10}11$ and you know: ...


1

To add to flawr's answer; regarding the "2nd part" - they're using the fact that $ 1 = \frac{5}{3} \times \frac{3}{5}$. So $(\frac{5}{3})^k = \frac{3}{5} \times \frac{5}{3} \times (\frac{5}{3})^k = \frac{3}{5} \times (\frac{5}{3})^{k+1}$


2

First you can assume that $F_k < (5/3)^k$ and $F_{k-1} < (5/3)^{k-1}$ so. $$F_{k+1} = \underbrace{F_{k}}_{<(5/3)^k}+\underbrace{F_{k-1}}_{< (5/3)^{k-1}} <(5/3)^k+ (5/3)^{k-1}$$ We can use $24/25 <1$ like so: $$F_{k+1} < \underbrace{24/25}_{<1} \cdot (5/3)^{k+1} < 1 \cdot (5/3)^{k+1}$$


-1

Base case: if $n=1$ then $1^3=1^2$. Induction step: you know that $$\sum_{i=1}^ni=\frac{n(n+1)}{2}$$ So: $$1^3+\cdots+n^3+(n+1)^3=(\frac{n(n+1)}{2})^2+(n+1)^3$$ So all what remains is to prove that: $$(\frac{n(n+1)}{2})^2+(n+1)^3=(\frac{(n+1)(n+2)}{2})^2$$


0

For binomial coefficients (as can be seen from the Pascal Triangle), the following identity holds: $$\require{cancel} {k\choose r}={k+1\choose r+1}-{k\choose {r+1}}$$ Summing by telescoping: $$\begin{align}\sum_{k=r}^{n}{k\choose r}&=\sum_{k=r}^{n}\left[{k+1\choose r+1}-{k\choose {r+1}}\right]\\ &=\quad {r+1\choose r+1} -\cancelto{0}{ {r\choose ...


2

Given that there are 5 types of person, each of whom sits to the left (or right) of ONE other person, this relationship can be shown as a square (person by neighbour). Also, the seating is going to be a continuous sequence where the 'left' person of the current pair will be the 'right' person of the next pair. Each neighbour relationship can be numbered 1 ...


2

Although this is a standard identity for binomial coefficients and @Did's answer was also standard, here's a combinatorial explanation: How many ways to choose 3 numbers out of $\{1,2,\cdots,q+2\}$ If $q+2$ is chosen, there are $\binom{q+1}{2}$ ways. If $q+2$ is not chosen, there are $\binom{q+1}{3}$ ways. Note that one can generalize the above argument ...


2

Plug $n=q+1$ and $k=2$ into the identity $${n\choose k+1}+{n\choose k}=\frac{n-k}{k+1}{n\choose k}+{n\choose k}=\frac{n+1}{k+1}{n\choose k}={n+1\choose k+1}.$$


1

Since you insist on proof by induction, maybe you could try it like this: Maximum number of inversions a) Prove by induction that the number of inversions is $\le \frac{n(n-1)}2$. $1^\circ$ If $n=1$, we have only one permutation which has no inversions. $2^\circ$ Suppose the claim is true for $n$ elements. If we add $(n+1)$-th element, then we have ...


5

An inductive proof can be made according to the following schema: $$A\to A(ABB)\to A(ACBCC)(ABB)\to A(ADBDCDD)(ACBCC)(ABB)\to A(AEBECEDEE)(ADBDCDD)(ACBCC)(ABB)$$ At each stage you have $n$ people of $n$ types, with all $n^2$ possible consecutive pairs.


4

You can construct a solution by induction. Assume you have a solution for $n$. There are $n$ doubles- put an $n+1$ between each pair and two of them in one of the spaces. Now all of $1$ to $n$ have the required neighbors except themselves so double one of each. So starting from $1221$ we go to $1233213$ and then to $112233213$ The next one is then to ...


16

It's a graph theory problem. What you're looking for is an Eulerian circuit in a complete directed graph of order $5$, consisting of five vertices $M,B,C,P,E$ and $25$ directed edges, one going from every vertex to every other vertex and also one looping from each vertex to itself. The existence of an Eulerian circuit (i.e. traversing each edge exactly once) ...


37

We prove this generalization: If there are $n$ people each of $n$ different specialties, then the $n^2$ people can be seated around a round table such that, if $A$ and $B$ are two different people with the same specialty, then the people sitting to the immediate left of A and to the immediate left of $B$ are of different specialties. (Our problem is the case ...


3

Prove by contradiction: suppose that no cubicles have at least $\frac{n}{m}$ programmers. Then the total amount of programmers is less than $n$, a contradiction. Also, the amount in each cubicle must be an integer, which proves the slightly stronger result with the ceiling function.


3

There is a way to solve this problem, but it requires time and work. The recurrence relation for this sequence is similar to that of the Fibonnaci sequence, in general, these types of sequences have closed forms in terms of a sum of exponentials of n. Here is how you can solve the problem: by the linearity of the recurrence relation, if $s_n$ is a sequence ...


2

Use a telescoping sum to get $$3a_n+2a_{n-1}+a_{n-2}=3a_2+2a_1+a_0.$$ Now it is easy to find the answer, by taking $n\to\infty$ in the above equation: $${3\cdot 1+2\cdot0+1\cdot0\over3+2+1}=\frac12.$$ Actually, we first have to prove that $\lim_{n\to\infty}a_n$ exists. With this method, you can also prove the general case.


0

Define the set $ NE = \{n x \ | \ x \in E\} $. Now clearly $ x \le \frac {K}{n}$ for every $x \in E$ and hence $ nx \le K $ whence it follows that $K$ is an upper bound for $ NE $. Then $l = \sup NE$ exists. Now consider the set $A = \{ n \in \Bbb N \ | n \ge l \ \} $. This set is non-empty since it contains $K$. By the Well-Ordering principle this set ...


1

I'll try to give a "philosophical" answer: If you take the so-called "Platonic" viewpoint which many mathematicians seem to share more or less, then mathematics is something which exists in some realm outside of us and can be "examined" by our minds. From this point of view the natural numbers are a reality that everybody experiences in the same way and ...


0

Mathematical induction is an instance of inheritance with respect to the relation $+1$. In W&R's PM, MI is the defining property of inductive cardinals. Some cardinals are inductive; some other cardinals, like $\aleph_0$, are noninductive. An inductive cardinal is defined as one which obeys MI starting from $0$, i.e. it is one which possesses every ...


2

For $n=1$ $11^{n+1}+12^{2n-1} = 11^2+12 =121+12=133$ which is divisible by 133 So, its true for $n=1$ Let us assume it is true for $n=k$ $\implies 11^{k+1}+12^{2k-1}=133s$ for some integer $s$ $\implies 12^{2k-1}=133s-11^{k+1}$ $\implies 12^{2k+1}=144(133s-11^{k+1})$ Now for $n=k+1$ $11^{k+2}+12^{2k+1}$ $=11^{k+2}+144(133s-11^{k+1})$ ...



Top 50 recent answers are included