New answers tagged

0

Using inclusion-exclusion we obtain immediately $$2^{2n} + \sum_{k=1}^n {n\choose k} (-1)^{k} 2^{2n-2k} = \sum_{k=0}^n {n\choose k} (-1)^{k} 2^{2n-2k} = (-1+4)^n \\ = 3^n.$$ Remark. This is for the case of the subsets not containing the forbidden pairs having any size. We now do the case of the subsets containing $n$ elements, with the same ...


2

You have set the requirement for subsets that do not contain both $v_i$ and $v_{n+i} $. However, in order for such a subset to have $n$ elements, it is clear that it must contain one of these. As such, every subset can be generated by combining all those choices between $v_i$ and $v_{n+i} $. Each of those choices is binary, and there are $n$ choices, ...


0

There are only $2^n$ numbers from $2^n+1$ to $2^{n+1}$. So the last part on the first line should be $$\frac12\frac{a_{2^n+1}+a_{2^n+2}+\cdots+a_{2^{n+1}}}{2^n}$$ very similar to the first part. Then, after applying the AM-GM on each of the two parts, you will need to apply the AM-GM again to combine the two parts into one.


0

If you want to present a proof in the way you discovered it you could indeed do it this way: To prove $A$, it suffices to prove $B$, which is equivalent to $C$, ... Or in symbolic form: We have:   $A$   $\ \Leftarrow B$   $\ \Leftrightarrow C$.   $\ \cdots$ In both cases, the logical reasoning is made clear ...


0

Not Directly an Inductive Proof Let $n\geq 2$ be an integer. Note that $F_n$ is the number of binary sequences of length $n-2$ without consecutive occurrences of $1$ (this part can be proven by induction). Since there are in total $2^{n-2}$ binary sequences of length $n-2$, it follows that $F_n\leq 2^{n-2}$. The equality holds only when $n=2$ and $n=3$. ...


2

Now, I'm going to restate what you said in the induction step, but simplify it more. The first statement was: $$F_k \leq 2^k$$ Notice how I left out the $\forall$ part. This is because you only add that in until after you've proven the statement. The second statement was: $$F_{k+1} \leq 2^{k+1}$$ The third statement was: $$F_{k+2} \leq 2^{k+2}$$ We assume ...


1

In answer to your specific points, 1) The inductive assumption is not being applied to the whole expression, but only to the first bracket, which runs to some smaller number than $k$. At that point, the intent is to show that the final element from the first bracket can be shifted into the start of the second bracket. 2) As above, the square bracket ...


1

1) How is it that Eq(2) contains $a_k$ but in that section of the proof the assumption is that the theorem is true for n≤k-1. Is not this assumption being overreached by the equation running to ak and therefore invalid? It's just a proof by complete induction: they assume that the result is true for $n \leq k-1$ and show it is also true for $n=k$. If the ...


0

Think of the theorem as being rewritten as follows: If $m$ is a natural number, $u_1,\dots,u_n, u_1',\dots,u_n'$ are designators, the string $u_1\dots u_n$ has exactly $m$ symbols, and $u_1\dots u_n$ and $u_1'\dots u_n'$ are compatible, then $u_i$ is $u_i'$ for $i=1, 2,\dots,n$. The proof is by induction on $m$. In the proof, the induction hypothesis is: ...


1

I think you have your wires crossed; particularly it seems like you're thinking about how the sum of the first $n$ odd numbers gives $n^2$. This is woefully incorrect. Here is how you should frame it: Suppose that $x_1,\ldots, x_n\ge 2$, then you want to show that $x_1\cdots x_n$ is odd if and only if $x_i$ is odd for all $i$. In terms of an induction ...


0

Proof by induction on $n$; Set your base induction for $n = 1$; which gives you $18 = 18.$ Suppose your equation is true for $n$. We are interested to prove its correctness for $n+1.$ So $3 + 3 \times 5 + \cdots + 3 \times 5^n + 3 \times 5^{n+1} = \frac{3 \times 5^{n+1} - 3}{4} + 3 \times 5^{n+1} = \frac{3 \times 5^{n+1} - 3 + 12 \times 5^{n+1} }{4} = \...


0

Let $S(n)$ be the statement: $3+3\cdot{5}+\cdots+3\cdot{5^{n}}=\dfrac{3\hspace{1 mm}(5^{n+1}-1)}{4}$; $n\geq{0}$ Basis step: $S(0)$: LHS: $3\cdot{5^{(0)}}=3$ RHS: $\dfrac{3\hspace{1 mm}(5^{(0)+1}-1)}{4}=\dfrac{3\hspace{1 mm}(5^{1}-1)}{4}$ $\hspace{35.5 mm}=\dfrac{3(4)}{4}$ $\hspace{35.5 mm}=3$ $\hspace{52.5 mm}$LHS $=$ RHS $\hspace{1 mm}$ (verified.) ...


0

Helping out with the problem. I'm stuck at the basis step. $p(n)$: $3+3 \cdot 5+ 3 \cdot 5^2+ \cdots +3 \cdot 5^n = \dfrac{3(5^{n+1} -1)}{4}$. Where $n \in \{0, 1, 2, \dots \}$. We can rewrite the predicate. $p(n)$: $\sum_0^n3\cdot5^n = \dfrac{3(5^{n+1} -1)}{4}$ Base case: Here you need to start at 0 because we only "induct" upwards. $p(0): \sum_0^...


0

If $\,P(n)\,$ is $\,\sum_{k=0}^{n} f(k)\, =\, g(n)$ then an inductive proof that $\,P(n)\,$ is true for all for all $\,n\ge \color{#c00}a$ has base case $\,n = \color{#c00}{a},\,$ i.e. the least value claimed true - the starting point of the induction. Your claim is for all nonnegative integers, i.e. for all $\,n\ge \color{#c00}0,\,$ so your base case is $\,...


3

As you want to prove for $n$ nonnegative and integer, your basis is $n=0$ You just have to prove that $\frac{3(5^{0+1} -1)}{4} = 3$ and it is true, because $\frac{3(5^{0+1} -1)}{4} = \frac{3(5 -1)}{4} = \frac{3.4}{4} = 3$ If you want to dofor $n = 1$: For $n=1$, you have that: $3 + 3.5 = 18$ and $\frac{3(5^{1+1} -1)}{4} = \frac{3(5^2 -1)}{4} = 18$


5

For $n=1$, since $3 + 3 \times 5^1= 3+15 = 18$, there is no problem with the righthand side being $18$ too. Note though that the base case is $n=0$, the condition being $n$ nonnegative, and then the lefthand side is $3$ as is the righthand side, which is $3 \times (5^{0+1}-1)/4 = 3$.


1

Using Induction on $n$, $\sum_{i=1}^{n+1}x_i$.$\sum_{i=1}^{n+1}1/x_i$$\geq n^2+x_{n+1}$$(\frac{1}{x_1}+$$\frac{1}{x_2}+....+$$\frac{1}{x_n}$)$+$$\frac{1}{x_{n+1}}$$(x_1+x_2+......+x_n)$ $=n^2+1+(\frac{x_{n+1}}{x_1}+\frac{x_1}{x_{n+1}})+....+ (\frac{x_{n+1}}{x_n}+\frac{x_n}{x_{n+1}})$$\geq n^2+1+2n=(n+1)^2$ Note: The minimum value of each term of type $(\...


3

Expand it out as $\sum_{i,j} x_i/x_j$, and use $t + 1/t \ge 2$ for $t > 0$


2

Assume known that $(x+y)^2\ge4xy,\forall x,y\in\Bbb R.$ Then suppose this inequality holds for $n.$ Now we have $$\begin{align}(\sum\limits_{i=1}^{n+1}x_i)\cdot(\sum\limits_{i=1}^{n+1}\frac{1}{x_i})&\ge(\sum\limits_{i=1}^{n})\cdot(\sum\limits_{i=1}^{n})+(\sum\limits_{i=1}^{n}x_i)\frac{1}{x_{n+1}}+x_{n+1}(\sum\limits_{i=1}^{n}\frac{1}{x_i})+1\\ &\ge n^...


0

Using AM-GM $$\sum_{k=1}^n x_k\ge n\sqrt[n]{x_1\cdot...\cdot x_n}$$ and $$\sum_{k=1}^n \dfrac{1}{x_k} \geq n\sqrt[n]{\frac1{x_1}\cdot...\cdot \frac1{x_n}}$$ Then $$\displaystyle \sum_{k=1}^n x_k\cdot \displaystyle \sum_{k=1}^n \dfrac{1}{x_k} \geq n^2$$


1

Let $A = \displaystyle \sum_{i=1}^n x_i, B = \displaystyle \sum_{i=1}^n \dfrac{1}{x_i}\implies P_{n+1} = \left(A+x_{n+1}\right)\left(B+\dfrac{1}{x_{n+1}}\right)= P_n+\dfrac{A}{x_{n+1}}+Bx_{n+1}+1\geq n^2+2\sqrt{AB}+1\geq n^2+2n+1 = (n+1)^2$.


4

The "well-ordering theorem" is the statement that for any set $X$, there is a relation $<$ on $X$ which is a well-ordering. This statement is equivalent to the axiom of choice. The "well-ordering principle" has (at least) two different meanings. The first meaning is just another name for the well-ordering theorem. The second meaning is the statement ...


1

Problems in Your Post You wrote, By Induction, Let $a_n=f_1+f_3+⋯+f_{2n−1}$ It is not clear from what you wrote what actually you are trying to prove. For example, you haven't defined what your $a_n$ is. You also haven't properly written what your actual statement is on which you are trying to apply induction. More precisely, to apply induction ...


0

Write $\ \ \ f_n\, =\ \ \color{#c00}1\cdot 5^n\, +\ \color{#0a0}2\cdot 3^{n-1} +1\,$ Then $\,f_{n+2} = \color{#c00}{25}\cdot 5^n + \color{#0a0}{18}\cdot 3 ^{n-1}+1\equiv f_n\pmod 8,\ $ by $\ \color{#c00}{25\equiv 1},\,\ \color{#0a0}{18\equiv 2}$ thus $\ 8\mid f_n\,\Rightarrow\,8\mid f_{n+2},\: $ so it is true, since the odd/even base cases $\,n=1,2\,$ ...


2

In response to a comment you made on Aravind's answer, you are absolutely allowed to go from $n$ to $n+1$, that is not where the problem in your proof is. However, your proof is still not working completely. What you have done is taken an arbitrary tree on $n$ vertices, which by your induction hypothesis has $n-1$ edges. You now form a new tree, (not an ...


2

Your induction proof is incorrect; the way induction works is (for example): Suppose we have a sequence $P(1),P(2),\ldots$ of statements and we wish to prove that $P(n)$ is true for all natural numbers $n$. After proving some base cases, say $P(1),\ldots,P(k)$, we consider an arbitrary $n>k$ and prove $P(n)$ assuming that the statements $P(1),P(2),\ldots,...


0

You can embbed the "$1+$" as the 0 th summand in the left summatory, and then your equality follows from the fact that $\left\lceil\frac{n-1}{2}\right\rceil=\left\lfloor n/2\right\rfloor$. You can see this easily splitting the cases where $n$ is even and odd. Edit:[You're very welcome] For the second equality just make the change of summation $k\leftarrow k-...


0

While this does not answer the specific question in the OP, I thought it would be instructive to present an approach that develops the inequality directly. To that end, we proceed. Note that we have $$\begin{align} \frac{1}{k^2}& \le \frac{1}{k(k-1)}\\\\ &=\frac{1}{k-1}-\frac{1}{k} \end{align}$$ Therefore, we can write $$\begin{align} \sum_{k=2}...


0

Your induction should be as follows: assume that this property holds for all $k≤n$. Then your inductive step for $n+1$ is: $$\frac{1}{3^2} +\ldots +\frac{1}{n^2}+\frac{1}{(n+1)^2}<\frac{1}{2^2}+\frac{1}{3^2}+\ldots +\frac{1}{n^2}$$ This holds as you can verify for yourself that $\frac{1}{2^2}>\frac{1}{(n+1)^2}$ for any $n≥2$. Since $\frac{1}{n}>\...


0

For the induction step, you assume the following: $$\frac{1}{2^2}+\frac{1}{3^2}+...+\frac{1}{n^2} < 1-\frac 1 n$$ and we want to prove the following: $$\frac{1}{2^2}+\frac{1}{3^2}+...+\frac{1}{n^2}+\frac{1}{(n+1)^2} < 1-\frac 1 {n+1}$$ Notice how we simply substituted $n+1$ into the original expression. We didn't do anything else; simply substituted. ...


0

Let $S(n)$ be the statement: $3+3\times{5}+3\times{5^{2}}+\cdots+3\times{5^{n}}=\dfrac{3(5^{n+1}-1)}{4}$; $n\geq{0}$ Basis step: $S(0)$: LHS: $3\times{5^{0}}=3\times{1}$ $\hspace{23 mm}=3$ RHS: $\dfrac{3(5^{(0)+1}-1)}{4}=\dfrac{3(5^{1}-1)}{4}$ $\hspace{37.5 mm}=\dfrac{3\times{4}}{4}$ $\hspace{37.5 mm}=3$ $\hspace{75 mm}$LHS $=$ RHS (verified.) ...


2

What the teacher has done is slowly work her way down inequalities. First she pulls out a three while introducing constant addition, and knocking the 3 down to a 2. Then she changes the 3 to a 2 (this makes it even smaller!). Then, she reduces a bit and subtracts one. Each one is greater than the other accept one that should be equal. Basically she bumps it ...


1

If you are willing to accept that for $z \notin \Bbb Z$ $$\Gamma (z) \Gamma (1-z) = \frac \pi {\sin \pi z}$$ then letting $z = \frac 1 2 - n$ leads to $$\Gamma \left( \frac 1 2 - n \right) \Gamma \left( \frac 1 2 + n \right) = \frac \pi {\sin \left( \frac \pi 2 - n \pi \right)} = \frac \pi {\cos n \pi} = (-1)^n \pi$$ and since you already know $$\Gamma \...


2

I think that the reflection formula $$ \Gamma(z) \Gamma(1 - z) = \frac{\pi}{\sin{(\pi z)}} \qquad z \not \in \mathbb{Z}, $$ should work better here, given that you already have computed $\displaystyle{\Gamma\left(k + \frac{1}{2} \right)}$.


1

Jack's answer is great, but if you are having difficult seeing the "since" portion of his answer, then consider the main portion of the inductive argument for establishing the identity that Jack gives: \begin{align} \sum_{k=1}^{n+1}\frac{k}{(k+1)!} &= \frac{n+1}{(n+2)!}+\color{green}{\sum_{k=1}^n\frac{k}{(k+1)!}}\tag{by defn. of $\Sigma$}\\[1em] &= \...


1

prove by induction that $$\sum_{k=1}^n\frac{k}{(k+1)!}=1-\frac{1}{(n+1)!}$$


5

It is a telescopic series: $$\sum_{k\geq 1}\frac{k}{(k+1)!}=\sum_{k\geq 1}\frac{(k+1)}{(k+1)!}-\sum_{k\geq 1}\frac{1}{(k+1)!}=\sum_{k\geq 1}\left(\frac{1}{k!}-\frac{1}{(k+1)!}\right)=\color{red}{1}$$ since: $$ \sum_{k=1}^{N}\frac{k}{(k+1)!} = 1-\frac{1}{(N+1)!}.$$


0

Let $S(n)$ be the statement: $3^{2n+2}+56n+55$ is divisible by $64$; $n\geq0$ Basis step: $S(0)$: $3^{2(0)+2}+56(0)+55=9+55$ $\hspace{37.25 mm}=64$, which is divisible by $64$ Inductive step: Assume $S(k)$ is true, i.e. assume that $3^{2k+2}+56k+55$ is divisible by $64$; $k\geq0$ $\hspace{59 mm}\Rightarrow 3^{2k+2}+56k+55=64A$; $A\in{\mathbb{N}}$ $\...


0

A good principle to go by is "Everything is unknown, until proven or taught otherwise." Another principle is "if something is unknown, then you cannot use it". And a third principle is "if you cannot use something, try something else". Induction says that P(n) will always be true if the base case is true and the induction step is true. What about if the ...


1

Let´s think a little bit about this: We know $1+...+n= \frac{n(n+1)}{2}$ for evey $n \in \mathbb{N}$. So if $4+5+...+n=\frac{n(n+1)}{3}$ for some $n$, we would have $(1+...+n)-(4+....+n)= \frac{n(n+1)}{2}-\frac{n(n+1)}{3} = 1+2+3=6$ And therefore $n(n+1)=36$. So we have proved this is false for every $n \in \mathbb{N}$


1

A field is a set of numbers together with "addition" and "multiplication" operations ( also some rules must apply to how these operations behave, but we skip them here ). In the $\mathbb{Z}_2$ field of numbers, which only has 2 numbers: 0 and 1, we can write these operations with small "tables": $$\begin{array}{|c|cc|}\hline+&0&1\\\hline0&0&...


3

This is the core part of the inductive argument (I'll omit comments--try to piece together how each step works and comment if something is unclear): \begin{align} \sum_{i=1}^{k+1}f_{2i}&=\sum_{i=1}^kf_{2i}+f_{2k+2}\\[1em] &= (f_{2k+1}-1)+f_{2k+2}\\[1em] &= (f_{2k+2}+f_{2k+1})-1\\[1em] &= f_{2k+3}-1\\[1em] &= f_{2(k+1)+1}-1. \end{align}


3

Hint. The inductive step is rather $$ f_2 + f_4 + \cdots + f_{2n}+\color{red}{f_{2n+2}}=\color{red}{f_{2n+3}}- 1, $$ then using the inductive hypothesis, we have to prove that $$ f_{2n+1}-1+\color{red}{f_{2n+2}}=\color{red}{f_{2n+3}}- 1. $$ Can you take it from here?


0

Nothing at all is stopping you from "adding 31 to that pile." In fact, I believe your goal is to show that you can form $n$ cents of postage whenever $n\geq30$ (when you have just 4-cent and 11-cent stamps at your disposal). Let $P(n)$ be the statement that you can form $n\geq30$ cents of postage using exclusively 4-cent and 11-cent stamps. Let $P(k)$ be ...


0

by using the divided differences method it is clear that the equation of above data is $$S=An^2+Bn+C$$ from the table ,we find the $A=2$ and $C=0$ hence $$S=2n^2+Bn$$ by using the $S=1$ when $n=1$ to get $B=-1$ so $$S=2n^2-n$$


1

The strong induction you might be thinking of for this problem would start with the four cases: \begin{align} 30&=11+11+4+4 \\ 31&=11+4+4+4+4+4 \\ 32&=4+4+4+4+4+4+4+4 \\ 33&=11+11+11 \\ \end{align} Then any subsequent case $k>33$ can run induction on the basis that there is a solution for $k-4$ and add a 4-cent stamp to that solution.


0

If only $4$ and $11$ cent stamps are available and you know you can create $n$ cent, what would allow you to create $n+1$ sents? If the way you obtain $n$ cents involves at least one 11-cent stamp, you can replace it with three 4-cents. Or if it involves eight 4-cents, you can replace these with three 11-cents. But in general you do not know if either of ...


1

I imagine the post on how to write a clear induction proof could be of great service to you. Bob's answer highlights the key points, but I thought I would provide another answer to possibly increase clarity. You have completed the base case and that's the first part. Great. Now, fix some integer $k\geq 0$ and assume that the statement $$ S(k) : \color{...


3

You are trying to show that $$\sum_{n=0}^{N}5^n=\frac{5^{N+1}-1}{4}$$ We can leave out the factor of $3$ since it just multiplies both sides. The base case is simple, you just have $1=1$. Now assume it is true for $N$. Then we have $$\sum_{n=0}^{N+1}5^n=\sum_{n=0}^{N}5^n+5^{N+1}=\frac{5^{N+1}-1}{4}+5^{N+1}=\frac{5^{N+1}-1+4\cdot 5^{N+1}}{4}=\frac{5\cdot ...


1

If $a_k = 6a_{k−1} − 8a_{k−2} $ and $a_n = 2^n(2^n + 1) $ for $n=k-1$ and $k-2$, then $\begin{array}\\ a_k &= 6a_{k−1} − 8a_{k−2}\\ &= 6(2^{k-1}(2^{k-1} + 1)) − 8(2^{k-2}(2^{k-2} + 1))\\ &= 6(2^{2k-2}+2^{k-1}) − 8(2^{2k-4}+2^{k-2})\\ &= 3(2^{2k-1}+2^{k}) − (2^{2k-1}+2^{k+1})\\ &= 3\cdot 2^{2k-1}+3\cdot 2^{k} − 2^{2k-1}-2^{k+1}\\ &= ...



Top 50 recent answers are included