# Tag Info

0

Hint: $$f(n)\cdot f(n+1) = \sum_{k=1}^nf(k)^2$$ $$\implies f(n+1)\cdot f(n+2) = f(n+1)\left[f(n+1) + f(n)\right]$$ $$= f(n+1)^2 + f(n)f(n+1) = \cdots$$

3

First, let's make the claim stronger - $\displaystyle \forall n\in\Bbb N:\ 1+\frac{1}{2^2}+\frac{1}{3^2}+\dots+\frac{1}{n^2}\le2-\frac{1}{n}<2$ Base case - $n=1$ is trivial. Step: assume the claim holds for $k$ and prove for $k+1$ $$\underbrace{1+\frac{1}{2^2}+\dots+\frac{1}{k^2}}_{\le 2-\frac{1}{k}\text{ by induction assumption}}+\frac{1}{(k+1)^2}\le ... 1 In the induction hypothesis, it was assumed that 2k+1 < 2^k,\forall k \geq 3, So when you have 2k + 1 +2 you can just sub in the 2^k for 2k+1 and make it an inequality. So that makes$$2k+1+2 < 2^k + 2$$and since it was assumed k\geq 3 we also know that 2 < 2^k. So now we have$$2k+1+2 < 2^k+2 < 2^k+2^k=2^{k+1}$$. Then by the ... 0 First, show that this is true for n=3: 2\cdot3+1<2^3 Second, assume that this is true for n: 2n+1<2^n Third, prove that this is true for n+1: 2(n+1)+1= \color\red{2n+1}+2< \color\red{2^n}+2= 2^n+\color\green{2^1}< 2^n+\color\green{2^n}= 2^{n+1} Please note that the assumption is used only in the part marked red. ... 0 You don’t need induction. Note that every time your automaton consumes a 1, it moves from a state in P_0 = \{q_1, q_q\} to a state in P_1 = \{q_2, q_4\}, and vice versa, and there is no other way to move between these two sets. We can “collapse” the automaton down to: ————> P0 <—————> P1 ↻ 1 ↺ 0 0 Thus, ... 0 I think the grammar consist of all words that (1) have an odd number of ones and (2) that end in a one. #2 is easy to see, since no arrows with a zero points to the final state. #1 can be proven too. I can come back later and write an induction for it. 0 HINT: Show by induction on n that the strings matching (b^*ab^*a)^n are precisely those strings that have 2n as and end in a. 0 Let E_n be the event that there are an even number of sixes rolled in n rolls, and O_n be the event that there are an odd number of sixes rolled in n rolls. Let X_i = 1 if roll i is a 6, otherwise X_i = 0. Clearly,$$\Pr[E_n] + \Pr[O_n] = 1$$for all n. Now, observe that$$\begin{align*} \Pr[E_n] &= \Pr[E_{n-1} \cap X_n = 0] + ...

0

Your method is correct but the induction hypothesis should be $$\text{Probabaility of an even number of sixes when you roll } k \text{ dice} = \frac{1}{2}\left[1+\left(\frac{2}{3}\right)^k\right]$$ (you have $n$ instead of $k$) and the thing you want to prove is $$\text{Probabaility of an even number of sixes when you roll } k+1 \text{ dice} = ... 1 You should be trying to get from \frac{5}{6} \cdot \frac{1}{2}[1+(\frac{2}{3})^n] + \frac{1}{6}(1 - \frac{1}{2}[1+(\frac{2}{3})^n]) to \frac{1}{2}[1+(\frac{2}{3})^{\bf{n+1}}] because that is the formula applied to n+1$$\frac{5}{6} \cdot \frac{1}{2}[1+(\frac{2}{3})^n] + \frac{1}{6}(1 - \frac{1}{2}[1+(\frac{2}{3})^n])=\frac 12+\frac 56\cdot \frac ...

2

As mentioned in the comments, this is probably easier to prove by using formulas for sums of powers. Nevertheless, if you want to proceed by induction, then you could do something like this: Your formula is equivalent to the statement that $P(n)$ is true for all $n\in\mathbb N$, where $$P(n):(3n+1)\sum_{k=1}^n k(k+1)^2-(3n+5)\sum_{k=1}^n k^2(k+1)=0$$ I ...

0

$$1\cdot 2^2 + 2\cdot 3^2 +\cdots+ n\cdot (n+1)^2 =2^3 -2^2 +3^3 - 3^2 +\cdots+(n+1)^3 -(n+1)^2 =\left(\frac{(n+2)(n+1)}{2}\right)^2 -\frac{(n+1)(n+2)(2n+3)}{6} =(n+1)(n+2)\left[\frac{n^2 +3n +2}{4} -\frac{2n+3}{6}\right]= (n+1)(n+2)\left[\frac{3n^2 +5n }{12}\right]=\frac{1}{12} n (n+1) (n+2) (3n+5)$$ $$1^2\cdot 2 + 2^2\cdot 3 +\cdots+ n^2\cdot (n+1) =1^3 ... 2 As pointed out by @RobertIsrael in the comments, in this particular problem, it's easier to do the induction on m because it's easy to assign an extra element in E to an element in F while it's not that straightforward the other way around. I must admit though, this problem can be easily solved without the help of induction. Note that you can assign ... 2 There is another way of thinking of this. Throw out the standard induction theorem, and replace it with this one: Any nonempty set of natural numbers has a smallest element. This seems obviously true, right? This is called the well-ordering principle, and it is equivalent to induction. Here's how you do induction with the well-ordering principle ... 1 It is hard to read the given argument. Roughly speaking, the idea looks ok but there is some confusion and it is unnecessarily complex. In particular, x>0 has no meaning in the context of a general field and I have never heard of the "monotonic axiom of multiplication". To answer the question: As here, we'll proceed by induction. For n=1 the ... 1 Think about Peano system (see footnotes) for defining natural numbers. You take an initial number, which you call 1, and then you say: Element 1 exists in the set. Any successor of an element n in the set, say suc(n), exists in the set. With these axioms, you construct the whole set of natural numbers. You don't need to prove such elements exist in a ... 2 "as long as we know that the state of a proposition being true for any positive integer k after Base number implies that proposition is true for integer k+1, we have to show that Pk is true. " 1) No, you don't. If I wanted to show that IF Godzilla were 10 times as large in all dimensions as a T. Rex THEN Godzilla would be weigh 1,000 times as much, I do ... 3 The part about assuming P_k is an application of basic rules of propositional logic. Suppose you have a proposition of the form A \implies B. One way you might be able to prove this proposition is by using the rule for Introduction of an Implication: Assume that A is true. Using A as a statement already known to be true, prove B. "Discharge" the ... 8 Your book is right. You have to show that$$P_k \implies P_{k+1}$$Because if you prove that and since you said it is true for base number, the proposition is automatically proved true for every n \in S. Let us see how! To prove "P_k \implies P_{k+1}" means you are proving that a particular proposition has a quality of being true for k+1 because of ... 4 What do we actually prove using induction theorem? Probably an example is needed here. Let's suppose you want to prove the little Gauss. Suppose we want to prove this Theorem for all n\in\mathbb{N}:$$ 1+2+3+ \cdots+ n = \sum_{k=1}^n k = \frac{n(n+1)}{2}$$The statement A(n) is thus given by:$$ \sum_{k=1}^n k = \frac{n(n+1)}{2} $$With induction this ... 1$$\frac{(a+1)^k}{a^k+1} \leq 2^{k-1}\iff\left(\frac{a+1}{2}\right)^k\leq\frac{a^k+1}{2}$$If k\in\mathbb{N}, f(x)=x^k is convex, i.e. f(\lambda x + (1-\lambda)y)\le\lambda f(x)+(1-\lambda)f(y) for all x,y, and \lambda\in[0,1]. Set x=1,y=a,\lambda=\frac{1}{2} to obtain the desired result. 1 The inequality of arithmetic and k-th degree mean states that$$ \frac{a_1+a_2+…+a_n}n\le \sqrt[k]{\frac{a_1^k+a_2^k+…+a_n^k}{n}} $$or$$ \frac{(a_1+a_2+…+a_n)^k}{a_1^k+a_2^k+…+a_n^k}\le n^{k-1} $$Now set n=2 etc. 4 Intuitively you can view this as a chain reaction, because once you show that \color{green}{P_0} is true, then by applying \color{blue}{P_k \Rightarrow P_{k+1}} repeatedly you can reach any number n \geq 0 and see that P_n is indeed true.$$\color{green}{P_0} \color{blue}{\Rightarrow} P_1 \color{blue}{\Rightarrow} \dots \color{blue}{\Rightarrow} ...

18

Induction is, intuitively, an outline of an infinite proof. You first prove $P(0)$, the base case. Then you prove $P(1)$ follows from $P(0)$. Then you prove that $P(2)$ follows from $P(1)$. Et cetera. In general, if you know that $P(k+1)$ follows from $P(k)$, and you know that $P(0)$ is true, then you know how to prove $P(n)$ for any natural number. ...

7

(Wanted to post as a comment, but it is too long :/) When we prove something by induction we prove that our claim is correct for a base case (for example, n=1). Afterwards we assume (not proving, only assuming) that our claim stands for some arbitrary value k and than, based on the assumption we prove it holds for k+1. Note that based on the proof of base ...

1

Note that $$\frac{n}{n+1} = 1 - \frac{1}{n+1},$$ $$\frac{n+1}{n+2} = 1 - \frac{1}{n+2},$$ so actually you just need to show that $$\frac{1}{n+1} > \frac{1}{n+2}.$$

0

Here is another way: Let $f(x) = { x \over x+1}$ and show that $f'(x) >0$ for all $x \ge 0$. Then $f$ is strictly increasing and so $f(n) < f(n+1)$ for all $n \ge 0$.

0

if you need induction: \begin{gather*} n(n+2)<(n+1)^2 \\ \begin{aligned} (n+1)(n+3)={}&n(n+2+1)+(n+3)=(n(n+2)+n+n+3)<(n+1)^2+2n+3={} \\ {}={}&(n^2+4n+4)=(n+2)^2. \end{aligned} \end{gather*}

0

It is a well-known inequality that, if $a,b,h>0$ then $$\begin{cases} \dfrac ab<1\implies \dfrac ab<\dfrac{a+h}{b+h}<1,\\ \dfrac ab>1\implies \dfrac ab>\dfrac{a+h}{b+h}>1. \end{cases}$$

0

Write $x\sqrt 3=m+\epsilon$ where $m\in \mathbb N$ and $0<\epsilon <1$. Then, on one hand, we have $\lfloor x+x\sqrt 3\rfloor =\lfloor (x+m)+\epsilon \rfloor=x+m$ and on the other $x+\lfloor x\sqrt 3\rfloor =x+\lfloor m+\epsilon \rfloor =x+m$ so the two sides are equal.

0

Use : if $0 < a < b \Rightarrow \dfrac{a}{b} < \dfrac{a+1}{b+1}$, with $a = k, b = k+1$, and once more $a = k+1, b = k+2$.

2

This only requires basic inequation manipulation ($n \in \mathbb{N}$): $${n \over n+ 1} < {n + 1\over n+ 2}$$ $$\iff n(n+2) < (n + 1)^2$$ $$\iff n^2+2n < n^2 + 2n + 1$$ $$\iff 0 < 1$$ Done.

6

You don't need induction, since it is enough to show $$n(n+2)<(n+1)^2$$

1

In order to prove it with strong induction you have to assume $n>14$ and that the result is true for every $k$ with $14\le k<n$, after having verified the case $n=14$. If $n=15$, or $n=16$, you've already done the computations. If $n>16$, then $n-3>13$, so $n-3=3a+5b$ by the (strong) induction hypothesis. Therefore $n=3(a+1)+5b$.

0

We don't need induction. Note $\lfloor n + u \rfloor = \lfloor u \rfloor + n$ for natural $n$. This follows since $\lfloor u \rfloor = u - \epsilon$ for $\epsilon \in [0,1)$. So we get $\lfloor n + u \rfloor = \lfloor n + \epsilon + \lfloor u \rfloor \rfloor$ = $n + \lfloor u \rfloor$ since $\lfloor u \rfloor + n ≤ n + \epsilon + \lfloor u \rfloor < ... 1 Here's how you do it! I've attached a picture I found on the internet since typing it takes time. This is a general approach that works for the sum of the$k^{th}$power of n consecutive integers for all possible values of n. Hope it helps :) 2 This works for sums of$p$th powers of$k$because of the fact that$(n+1)^{p+1}-n^{p+1},$when expanded by the binomial theorem, will have no$n^{p+1}$term, and so when summed only uses powers up to the$p$th power. Also before expanding it, its sum "telescopes" (all terms cancel but two, or all but one if you sum starting at$0.$). Also once you accept ... 5 The last equation reads $$d_0=-2\sin^2\left(\frac x2\right)=\cos(x)-1.$$ Then eliminating$d$from the second and the third, $$d_k=c_{k+1}-c_k,\\ c_{k+1}-2c_k+c_{k-1}=2(\cos(x)-1)c_k.$$ If we assume that$c_k=\cos(kx)$, then after some simplification, $$\cos(kx+k)-2\cos(kx)+\cos(kx-x)=2\cos(kx)\cos(x)-2\cos(kx)\\=2(\cos(x)-1)\cos(kx).$$ Hence ... 0 Another approach is to show that $$\left(1+\frac1n\right)^{2n}=\left(\frac{n+1}{n}\right)^{2n}>2.$$ The inequality follows directly from the binomial theorem. 2 Hint: In the third step, try multiplying the RHS of what you got in the second step with$(a+b)$. That will create two distinct series of sums, say$S_1$and$S_2$, where $$S_1=a(a^k+ka^{k-1}b+\cdots+kab^{k-1}+b^k)=a^{k+1}+ka^kb+\cdots+ka^2b^{k-1}+ab^k$$ $$S_2=b(a^k+ka^{k-1}b+\cdots+kab^{k-1}+b^k)=a^kb+ka^{k-1}b^2+\cdots+kab^k+b^{k+1}$$ If you leave out the ... 0 This is just binomial theorem! See inductive proof in this wikipedia page https://en.wikipedia.org/wiki/Binomial_theorem 1 Set$n=k+1$then your expression is equivalent modulo 3 to $$n^3+7n+3 \equiv n+7n+3 \equiv 8n \equiv -n \pmod{3}.$$ In particular, this is a multiple of$3$iff$3$divides$k+1$. 1 Take$k+1=j$and take modulo$3$. So the question is if$j^3+j$is a multiple of$3$, but$j^3+j=j(j^2+1)$, which is never a multiple of$3$if$j$isn't. 4 The statement is not true. Take$n=1$as a counter example. Since it's not true, you won't manage to prove it (by induction or otherwise). 2 Rather than look for a least element, consider the following proposition: $$\text{If A\subsetneqq \{0,\dotsc n\} then there is a greatest m\le n such that m\notin A}.\tag{*}$$ We'll prove (*) by induction below, but first let's use it to prove your statement (or, a correct version of it). Call a set$A\subseteq \Bbb N$downward closed if for all ... 1 The problem is that your ordering is wrong. You need to order your set the opposite direction as you normally would. A simple way to see that this holds though is as follows. Consider a set$S=\{0,\ldots, n\}\subset\mathbb{Z}$that satisfies backwards induction for some property$P$. Define $$S'=\{k\in \{0,\ldots n\}: \exists s\in S(k=n-s)\}$$ We see that ... -1 A) If$k^2+5k+1$is even, $$(k+1)^2+5(k+1)+1=(k^2+2k+1)+(5k+5)+1=(k^2+5k+1)+2k+6$$ is even as well. B) No, you need a base hypothesis. C) Obviously$0^2+5\cdot0+1$is not even (base hypothesis), and by adapting A), if$k^2+5k+1$is not even, neither is$(k+1)^2+5(k+1)+1$(induction). 1 It is not (necessarily) about induction...$f(x)=(x-\alpha)g(x)$because$f(\alpha)=0f'(x)=(x-\alpha)g'(x)+g(x)$.. As$f'(\alpha)=0$we have$g(\alpha)=0$so,$g(x)=(x-\alpha)g_1(x)$and so$f(x)=(x-\alpha)^2g_1(x)$... Repeat this... Can you continue from here? 0 Here is an inductive proof: For$n=2$we get $$1-\frac{1}{2^{2}}=\frac{2+1}{2*2}=\frac{3}{4}$$ Let$n=k>2$and $$(1-\frac{1}{2^{2}})(1-\frac{1}{3^{2}})...(1-\frac{1}{k^{2}})=\frac{k+1}{2*k}$$ and now the induction step: Let$n=k+1$, then ... 0 How to start a proof by induction? What a straight line! You start at the beginning. ... Then you show that the middle flows, and conclude that the end is inevitable. But seriously... You start with$n = 2$. Prove that$(1 - 1/4) = (2+1)/2*2\$. That's the initial or base step. Then you do the induction step. You prove that if ...

Top 50 recent answers are included