Tag Info

New answers tagged

1

I think we can do as follows: suppose the claim is true up to $\;n\in\Bbb N=\Bbb Z_{\ge0}\;$, and we shall show for $\;n+1\;$ . We have two cases, and we assume $\;n=b(\sigma_0\sigma_1\ldots\sigma_d)\;$: 1) $\;n\;$ is even: then$\;\sigma_0=0\;$ (why?) , and thus $$b(1\sigma_0\sigma_1\ldots\sigma_d)=n+1$$ 2) $\;n\;$ is odd: then $\;\sigma_0=1\;$ (again, ...


2

Yes, this proof is correct. Nice work!


1

Note that $$(g_1g_2\cdots g_n)(g_n^{-1}g_{n-1}^{-1}\cdots g_1^{-1})=(g_1g_2\cdots g_{n-1}(g_ng_n^{-1})g_{n-1}^{-1}\cdots g_1^{-1})=(g_1g_2\cdots g_{n-2}(g_{n-1}g_{n-1}^{-1})g_{n-2}^{-1}\cdots g_1^{-1})=\cdots=(g_1g_1^{-1})=1$$ This can be formalized into an induction proof.


0

This exercise shows that the sum of the reciprocals of the squares converges to something at most $2$; in fact, the series converges to $\frac{\pi^2}{6}$. For $n\geq 1$, denote the statement in the exercise by $$ S(n) : 1 + \frac{1}{4} + \frac{1}{9} + \cdots + \frac{1}{n^2} \leq 2 - \frac{1}{n}. $$ Base step ($n=1$): Since $1=2-\frac{1}{1}, S(1)$ holds. ...


0

$n2^{n+2}+2= \sum_{i\leq n+1} i2^î= \sum_{i\leq n} i2^î +(n+1)2^{n+1}= [(n-1)2^{n+1}+2]+(n+1)2^{n+1}$ by induction hypothesis. Then subtracting the $i\leq n$ sum from both sides you are done.


0

There's no need for induction. Note that when you start increasing any $x_i$, the left side increases slower (or equally) because the product of the other factors besides $(x_i+1)$ is less or equal to $1$. So without loss of generality, all the variables are $0$ and the inequality holds.


1

Why not some properties of powers of (natural) numbers: $$\forall\,a,b,m,n\in\mathbb{N}\setminus\{0\},\quad a^m\cdot a^n=a^{m+n},\quad (a^m)^n=a^{mn},\quad a^n\cdot b^n=(ab)^n.$$ Another one, which is not totally elementary as you meant it but I think may be very formative in secondary school level is the following: If $p$ is a polynomial in variable ...


2

Why not directly instead of cases? $$\prod_{k=1}^n(1+x_k)=\prod_{k=1}^{n-1}(1+x_k)\cdot(1+x_n)\stackrel{\text{ind. hyp.}\,+\,(1+x_n)\ge0}\ge(1+x_1+\ldots+x_{n-1})(1+x_n)=$$ $$=1+\sum_{k=1}^n x_k+\sum_{k=1}^{n-1}\overbrace{x_kx_n}^{\ge 0}\ge1+\sum_{k=1}^n x_k$$ and we're done


4

We know that $$(1+x_1)\cdots(1+x_n) \geq 1+x_1+\ldots +x_n$$ If we now multiply the inequality above by $(1+x_{n+1}) \geq 0$ we obtain $$(1+x_1)\cdots(1+x_n)(1+x_{n+1}) \geq (1+x_1+\ldots +x_n)(1+x_{n+1})\\= (1+x_1+\ldots +x_n) + x_{n+1} + x_{n+1}(x_1+\ldots +x_n) \geq 1 + x_1 + \ldots + x_{n+1}$$ where the last inequality follows from the fact that $x_i ...


0

First, show that this is true for $n=1$: $1+\sum\limits_{i=1}^{1}i\cdot{i!}=(1+1)!$ Second, assume that this is true for $n$: $1+\sum\limits_{i=1}^{n}i\cdot{i!}=(n+1)!$ Third, prove that this is true for $n+1$: $1+\sum\limits_{i=1}^{n+1}i\cdot{i!}=1+\sum\limits_{i=1}^{n}i\cdot{i!}+(n+1)\cdot(n+1)!$ ...


3

$$\begin{align}1 + \sum_{i=1}^{k+1} ii!& = \color{green}{1 + \sum_{i=1}^{k} ii!} + (k+1)(k+1)! \\&=\color{green}{(k+1)!} + (k+1)(k+1)! \\&= (k+1 +1 )(k+1)! \\&= (k+2)(k+1)! \\&= (k+ 2)! \end{align}$$


2

It’s easier to understand if you word backwards. Suppose that such a tree has depth $d$; what are the maximum and minimum possible numbers of nodes? A perfect binary tree of depth $d$ has $$1+2+\ldots+2^d=2^{d+1}-1$$ nodes; that’s clearly the maximum. You can remove at most $2^{d-1}$ of the nodes in the last level and still have a quasi-complete binary ...


0

I am going to provide a different way of going about it--this is essentially Brian M. Scott's proof in reverse. As people have pointed out, if you can show that $n! > 2^n$, then you will have shown that $n! \geq 2^n$ (in this sense, you can think of $>$ as stronger than $\geq$ because $>$ implies $\geq$). When considering $n! \geq 2^n$ and how you ...


3

Basic non-inductive proof: For $k\ge1,$ $$k\cdot\binom nk=k\cdot\frac{n!}{n!\cdot k!}=k\cdot\frac{n\cdot(n-1)!}{\{(n-1)-(k-1)\}!\cdot k\cdot(k-1)!}=n\binom{n-1}{k-1}$$ $$\implies S=\sum_{k=1}^nk\binom nk=\sum_{k=1}^nn\binom{n-1}{k-1}$$ Set $k-1=r$ $$\implies S=n\sum_{r=0}^{n-1}\binom{n-1}r=n(1+1)^{n-1}$$


2

Another non-inductive proof: If $s =\sum\limits_{k=1}^p{k}{p\choose k} $, then $s =\sum\limits_{k=0}^p{k}{p\choose k} =\sum\limits_{k=0}^p(p-k){p\choose p-k} =\sum\limits_{k=0}^p(p-k){p\choose k} $ so $2s =\sum\limits_{k=0}^p{k}{p\choose k} +\sum\limits_{k=0}^p(p-k){p\choose k} =\sum\limits_{k=0}^p(k+(p-k)){p\choose k} =\sum\limits_{k=0}^p p{p\choose k} ...


2

Hint: $$(1+x)^n=1+C_{n}^{1}x+C_{n}^{2}x^2+\cdots+C_{n}^{n-1}x^{n-1}+x^n$$ Differentiate both sides in terms of $x$ $$n(1+x)^{n-1}=C_{n}^{1}+2C_{n}^{2}x+3C_{n}^{3}x^2+\cdots+(n-1)C_{n}^{n-1}x^{n-2}+nx^{n-1}$$ And let $x=1$.


0

First note that we can use the stronger relation $>$ than $\geq$ for the given inequality when we assume $x\neq 0$ (this inequality is actually known as Bernoulli's inequality). I will try to outline a clear proof below. Claim: Fix $x\in\mathbb{R}$ with $x>-1$ and $x\neq 0$. For each $n\geq 2$, let $S(n)$ be the statement that $(1+x)^n > 1+nx$ ...


0

Let me just write what you wrote with minor variations and extra explanations. First the inequality is true when $n=1$ since then we have $1+x\ge1+x$. (You teacher says $n\ge2$ but it is also true for $n=1$ or even for $n=0$, I prefer to start with $n=1$ it is easier.) So now using induction, assume it is true for some $n\ge1$ and prove it for $n+1$. ...


0

Inductive step: $$ (1+x)^n \geq 1+nx $$ Proof step(?) $$ (1+x)^{n+1} =(1+x)^n (1+x) \geq (1+nx)(1+x) = 1+nx +nx^2+x \geq 1+nx +x $$ The first inequality is by the inductive step, the second is due to the positivity of $nx^2$.


1

An idea to complete the proof: You assume $\;(1+x)^n\ge 1+nx\;$ , and you have to prove $$\color{red}{(1+x)^{n+1}\ge1+(n+1)x}$$ Let us take the left side and develop it using the inductive hypotheses: $$(1+x)^{n+1}=(1+x)^n(1+x)\stackrel{\text{Ind. Hyp.}}\ge(1+nx)(1+x)$$ So it is enough to prove ...


-1

Hint: $a^{n+1} = a \cdot a^n < a \cdot b^n < b \cdot b^n = b^{n+1}$.


1

Creating a story to prove a combinatorial identity by double counting is always fun. LHS: Choose $k$ among $n$ objects, and then choose one favorite object among the $k$. Here, $k$ should be at least 1, and can be as much as $n$. RHS: Start by choosing one favorite among the $n$ objects. Then for each of the $n-1$ remaining objects, decide one at a time ...


2

Let $S = \sum_{k = 1}^n k\binom{n}{k} = \sum_{k = 0}^n k\binom{n}{k}$. Then $$S = \sum_{k = 0}^n \left[n\binom{n}{k} - (n-k)\binom{n}{k}\right] = \sum_{k = 0}^n \left[n\binom{n}{k} - (n-k)\binom{n}{n-k}\right] = n\sum_{k = 0}^n \binom{n}{k} - S.$$ Solving for $S$, we obtain $$S = \frac{n}{2}\sum_{k = 0}^n \binom{n}{k} = \frac{n}{2}\cdot 2^n = n\cdot ...


-1

They gave you the hint ! Test with $n=4$: $$(1+x)^4=\binom40x^0+\binom41x^1+\binom42x^2+\binom43x^3+\binom44x^4.$$ After derivation, $$4\cdot(1+x)^3=0+1\cdot\binom41x^0+2\cdot\binom42x^1+3\cdot\binom43x^2+4\cdot\binom44x^3.$$ Don't you see the connection ?


7

Using the binomial identity shown in $(3)$, we have $$ \begin{align} k\binom{n}{k} &=\binom{k}{1}\binom{n}{k}\\ &=\binom{n}{1}\binom{n-1}{k-1}\tag{1} \end{align} $$ Now sum $(1)$: $$ \begin{align} \sum_{k=1}^nk\binom{n}{k} &=\sum_{k=1}^n\binom{n}{1}\binom{n-1}{k-1}\\ &=n2^{n-1}\tag{2} \end{align} $$ Binomial Identity $$ \begin{align} ...


6

$(1+x)^n=\sum\limits_{k=0}^n {n \choose k}x^k$. Now differentiate both sides with respect to $x$ and put $x=1$.


0

Use the fact that $\gcd(a_n,b_n)$ must divide any $\mathbb Z$-linear combination of $a_n$ and $b_n.$ With that, we see from 1. that we must indeed have $\gcd(a_n,b_n) = 1.$


0

Your goal is to prove the statement $S(n)$ for all $n\geq 1$ where $$ S(n) : 1^3 + 2^3 +3^3 +\cdots + n^3 = \left[\frac{n(n+1)}{2}\right]^2. $$ Using $\Sigma$-notation, we may rewrite $S(n)$ as follows: $$ S(n) : \sum_{r=1}^n r^3 = \left[\frac{n(n+1)}{2}\right]^2. $$ Base step: The statement $S(1)$ says that $(1)^3 = (1)^2$ which is true because $1=1$. ...


1

You're on the right track! The simplest way to show the last line is to foil out the terms on the left and right and note that they're equal (tedious, I know--but it'll get you what you need). If you haven't done so already, try proving these formulas with induction (for extra practice; they're a little easier): $$\sum_{k=1}^n k = \frac{n(n+1)}{2}\quad\quad ...


1

**HINT:**$$\left(\frac{k(k+1)}{2}\right)^2+(k+1)^3=\frac{k^2(k+1)^2}{4}+(k+1)^3$$$$=\frac{k^2(k+1)^2+4(k+1)^3}{4}$$$$=\frac{(k+1)^2(k^2+4(k+1))}{4}$$$$=\frac{(k+1)^2(k^2+4k+4)}{4}$$$$=\frac{(k+1)^2(k+2)^2}{4}$$Hopefully you can complete the proof from here...


1

Show that, for every $n\geq2, 3^n >n(n-1)$. Well, I started by showing the base case($n = 2$): $3^2 > 2$ Now assume that the statement we are attempting to prove is actually true up to $n$; we claim that $P(n+1) = 3^{n+1} > (n+1)(n)$ is true. Well, on the LHS you get $(3^n)(3) > (n)(n-1)(3)$ (true from our assumption) but for all $n ...


0

By definition (no use of a theorem), if $d$ divides $k$, then $k=d\gamma$, where $\gamma\in\mathbb{Z}$. Also, if $d$ divides $n$, then $n=d\eta$, where $\eta\in\mathbb{Z}$. Now consider that \begin{align} 8k-3d &= 8(d\gamma)-3(d\eta)\\[0.5em] &= d(8\gamma)-d(3\eta)\\[0.5em] &= d(8\gamma-3\eta)\\[0.5em] &= d\phi, \end{align} ...


0

I will outline a simplified version that is more drawn out but probably answers your question more clearly. Your goal is to prove that the statement $P(n)$, that is, $$ P(n) : 1+6+11+\cdots+(5n-4)=\frac{n(5n-3)}{2} $$ holds for all $n\geq 1$. Base step: As you noted, check the $n=1$ case for the base step. Using $n=1$, we have that $$ ...


0

A Proof Without Using Induction: $$\begin{align}LHS&=1+6+11+\cdots +(5n-4)\\&=[1+(5\times 1-5)]+[1+(5\times 2-5)]+\cdots +[1+(5\times n-5)]\\&=n+5\cdot\frac{n(n+1)}{2}-5n\\&=n+5\cdot\frac{n(n-1)}{2}\\&=\frac{n}{2}\cdot(2+5n-5)\\&=\frac{n(5n-3)}{2}\\&=RHS\end{align}$$


0

Suppose the formula for $n$ is known. Writing $(1-x)^{-(n+1)}=\sum_kc_kx^k$ (with certainly $c_0=1$) one must have $(1-x)^{-n}=(1-x)\sum_kc_kx^k=1+\sum_{k>0}(c_k-c_{k-1})x^k$. That gives us the recurrence relation $c_k-c_{k-1}=\binom{k+n-1}{n-1}$ with $c_0=1$. It follows from Pascal's recurrence that $c_k=\binom{k+n}n$ satisfies this recurrence relation. ...


1

So you need to prove $$ \sum_{k=1}^n (5k-4) = n(5n-3)/2 $$ by induction. You start by checking that the formula works for some $n$ ($n=1$ for example) $$ n=1 \Rightarrow \sum_{k=1}^1 (5k-4) = (5-4) = 1 = (5-3)/2 $$ which is true. Then your goal is to prove that the formula holding for $n$ implies that it holds for $n+1$. Start by writing the $n+1$ case ...


0

$$1=1(5\times 1-3)/2$$ $$1+6+11+\cdots+(5k-4)=^?k(5k-3)/2$$ $$1+6+11+\cdots+(5k-4)+(5k+1)=^?(k+1)(5k+2)/2$$ $$k(5k-3)/2+(5k+1)=^?(k+1)(5k+2)/2$$ $$k(5k-3)/2+(5k+1)=^?(k+1)(5k+2)/2$$ After some algebra... $$(5k^2+7k+2)/2==(5k^2+7k+2)/2$$ which is true.


1

First, show that this is true for $n=1$: $\sum\limits_{i=1}^{1}5i-4=\dfrac{5-3}{2}$ Second, assume that this is true for $n$: $\sum\limits_{i=1}^{n}5i-4=\dfrac{n(5n-3)}{2}$ Third, prove that this is true for $n+1$: $\sum\limits_{i=1}^{n+1}5i-4=\left(\sum\limits_{i=1}^{n}5i-4\right)+5(n+1)-4$ ...


0

You have the induction assumption $$1+2+\ldots+(5(n-1)-4)=\frac{(n-1)(5(n-1)-3)}{2}$$ Add $5n-4$ to that... And you should get $P(n-1)\Rightarrow P(n)$ and this completes the induction


1

$$p(1): 1=\frac{1(5(1)-3)}{2}\\p(k):1+6+11+...+(5n-4)=\frac{n(5n-3)}{2}\\$$now try to prove $$p(k+1):1+6+11+...+(5n-4)+(5(n+1)-4)=\frac{(n+1)(5(n+1)-3)}{2}\\$$


2

let $a_{i}-1=b_{i},i=1,2,\cdots,n$, $$\Longleftrightarrow (b_{1}+2)(b_{2}+2)\cdots(b_{n}+2)\ge\dfrac{2^n}{n+1}(b_{1}+b_{2}+\cdots+b_{n}+n+1)$$ $$\Longleftrightarrow 2^n\left(1+\dfrac{b_{1}}{2}\right)\left(1+\dfrac{b_{2}}{2}\right)\cdots\left(1+\dfrac{b_{n}}{2}\right)\ge\dfrac{2^n}{n+1}(b_{1}+b_{2}+\cdots+b_{n}+n+1)$$ $$\Longleftrightarrow ...


1

First, show that this is true for $n=1$: $2^1-1=\sum\limits_{i=0}^{1-1}2^i$ Second, assume that this is true for $n$: $2^n-1=\sum\limits_{i=0}^{n-1}2^i$ Third, prove that this is true for $n+1$: $2^{n+1}-1=2\cdot2^n-1$ $2\cdot2^n-1=2\cdot2^n-2+1$ $2\cdot2^n-2+1=2\cdot(2^n-1)+1$ $2\cdot(2^n-1)+1=1+2\cdot(2^n-1)$ ...


0

Although the hint by Guest is quite good, as graydad pointed out, I imagine you are probably struggling with some summation manipulation (or am I wrong?). Here's a brief sketch (I imagine you can fill in all of the fine details and make the argument flow like a written proof should): \begin{align} 2^{k+1}-1 &= 2\cdot(2^k-1)+1\\[1em] &= ...


0

Guest has given a very good hint. Alternatively, you can generalize: For any $x,y \in \Bbb{R}$ then $$x^n-y^n = (x-y)\sum_{i=0}^{n-1}y^ix^{n-1-i}$$ If you prove this by induction, then your proof follows as a special case of $x=2, y=1$. Your original proof is probably easier than this one, but this one is a good result to have regardless.


0

Hint : $2^{n+1}-1=2(2^n-1)+1$.


0

Let $S \subseteq N$ be non-empty, and define: $R = \{x \in N : x \le y, \forall y \in S\}.$ Then $0 \in R$ since $0 \le y$ $\forall y \in N$, in particular $\forall y \in S$. Since S is non-empty, there is a $y \in S$; this implies $y + 1 \notin R$: otherwise we would have $y + 1 \le y$, [Perhaps you can disprove this with PEANO'S AXIOMS] Thus $R$ contains ...


1

You might consider this to be a bit cheating, but here is a proof using only induction and one additional inference. Lemma. If $A\subseteq\Bbb N$ has a maximal element, then $A$ has a minimal element. Proof. First note that $A$ has a maximal element, so it is non-empty. Now we prove by induction on $n$: If $\max A=n$ then $A$ has a minimal element. If ...


2

It follows from the following. Dedekind's Recursion Theorem: Given a set $X$, $x\in X$ and a map $f\colon X\to X$, there exists (one and only one) function $h\colon \mathbb N\to \mathbb X$ such that $h(0)=x$ and $\forall m\in \mathbb N(h(m+1)=f(h(m)))$. (For a proof see, for instance, Thomas Jech's Introduction to Set Theory, (chapter 3, section 3). I ...



Top 50 recent answers are included