Tag Info

New answers tagged

2

Our induction assumption is that the formula holds for all $i\le n+1$, and we show that the formula holds for $i=n+2$. So we are using what is called strong induction. Actually, it is enough to have as induction assumption that the formula holds at $n=k$ and $n=k+1$, and show it holds at $n=k+2$. So we know that for a certain $k$ we have ...


0

Notice that (we can prove it using Gauss method) $$\sum_{k=p}^q k=\frac{(q-p+1)(p+q)}2$$ so we find that $$S(n)=\frac{(n^2-(n-1)^2)(n^2+(n-1)^2+1)}{2}=2\,{n}^{3}−3\,{n}^{2}+3\,n−1\\=n^3+(n-1)^3$$


1

Define $\Delta$ the discrete differential operator by its action on $f:\mathbf Z\to\mathbf R$: $$\Delta f(x)=f(x)-f(x-1).$$ It is clear that for every polynomial $P\in\mathbf R_1[X]$ of degree at most 1, $\Delta P(X)=P'(X)$. Therefore, for every polynomial $P\in\mathbf R_n[X]$, $\Delta^nP=P^{(n)}$. We will now show by induction that ...


0

Since you're asked to prove a property for $n\ge 2$, the base case is the $n=2$ case: $$a_2\ge 2^{g(2)}$$ This is very easy (in fact trivial) to prove once you unfold the defintions of $a_2$ and $g(2)$.


2

Try expanding $2(k+1)^2 + 3(k+1)$ in order to compare it with $6k^2 + 9k$ (I.e., what you need to ensure that $6k^2 + 9k \geq 2(k+1)^2 + 3(k+1))$: $$\begin{align} 2(k+1)^2 + 3(k+1) & = 2(k^2 + 2k + 1) + 3k + 3 \\ &= 2k^2 + 4k + 2 + 3k + 3 \\ &= 2k^2 + 7k +5\end{align}$$ Now, all that remains (while keeping in mind that $\bf k\geq 4)$ is to show ...


2

$3^n\geq2n^2+3n$ (1) $n=4$ $81\geq44$ (2) Assume true for $n=k$ ,Therfore we have : $3^k\geq2k^2+3k$ (3) Then for $n=k+1$ $3^{k+1}\geq2(k+1)^2+3k+3$ Simplifying this gives: $3(3^k)\geq2k^2+7k+5$ Now to prove this ^^^ you can subsititute what we assumed in (2) to show this inequality stands. $3^k\geq2k^2+3k$ So.. $3(2k^2+3k)\geq2k^2+7k+5$ ...


2

For the induction step we have , assuming the induction hypotheses : $3^k \ge 2k^2+3k$, that : $3^k(3)=3^{k+1}>(2k^2+3^k)(3)=6k^2+9k$ which, due to the fact that $k \ge 4$, is : $\ge 6k^2+7k+8 \ge 2k^2+7k+5 = 2(k+1)^2+3(k+1)$.


2

From $3^{n}\geq2n^{2}+3n$ it must be proved that $3^{n+1}\geq2\left(n+1\right)^{2}+3\left(n+1\right)$. (i.e. $P(n)\Rightarrow P(n+1)$) Equivalently from $3^{n+1}\geq3\left(2n^{2}+3n\right)$ it must be proved that $3^{n+1}\geq2\left(n+1\right)^{2}+3\left(n+1\right)$. That comes to proving that ...


2

Remember that $k \geq 4$. Then: $$6k^2 + 9k \geq 2k^2 +9k \geq 2k^2 +7k + 5 = 2(k+1)^2 + 3(k+1)$$


1

Denote set of the subsets of $\left\{ 1,\dots,n\right\} $ that do not contain two consecutive numbers by $\mathcal{A}_{n}$. Then $A_{n}$ is the cardinality of $\mathcal{A}_{n}$. Note that $\mathcal{A}_{n}=\mathcal{A}_{n-1}\cup\left\{ T\cup\left\{ n\right\} \mid T\in\mathcal{A}_{n-2}\right\} $. These sets are disjoint so that $A_{n}=A_{n-1}+A_{n-2}$.


1

Divide the column into sections at height 0, 1, 2, 4, 8,... so that the first section is [0, 1) and the n'th section (n >1) is the height interval $[2^{n-2}$ to $2^{n-1})$. Now propose the inductive hypothesis that starting in the N'th section the climber falls into the danger zone in at most 2N steps (in fact it will be less than 2N, but this works easily ...


0

Hint: Let $a_k$ be your height after $k$ jumps and falls (so each step consists of a jump and the subsequent fall). So $a_0$ is your starting height. Set up a recursion for $a_k$ for $k\ge 1$. Then prove that for any starting height $a_0$ the sequence $\{a_k\}_{k=0}^\infty$ is monotone and bounded (this is where you would do induction), and hence ...


0

Hint: $$a^n - b^n = (a - b)(a^{n-1} + a^{n-2}b + \cdots+ ab^{n-2} + b^{n-1}$$


1

We use induction on $n$, with a base case of $n=1$. Base Case We are given that $a-b$ is a multiple of $c$. Equivalently, there exists a $k_1 \in \mathbb{N}$ such that $$k_1c = a-b = a^1-b^1$$ Inductive Step Suppose that $a^n-b^n$ is a multiple of $c$. Then there exists a $k_2 \in \mathbb{N}$ such that $a^n-b^n = k_2c$. As David pointed out, ...


4

The inequality holds for $n\in\{1,2\}$. Assume $n\geq 3$. Apply the AM-GM inequality to the sequence of $n$ numbers $$1, 1, \dots, 1, 2, \sqrt{\frac{n}{2}}, \sqrt{\frac{n}{2}}$$ to obtain $$n^{1/n} \leq \frac{n-1+\sqrt{2n}}{n}$$ and your inequality follows.


1

Preliminary comment: The result follows immediately from the meaning of binomial distribution. But the problem is asking for a computation. We deal with the induction step. Assume that the sum $Y_n=X_1+\cdots+X_n$ has binomial distribution. This means that for all suitable $i$, we have $$\Pr(Y_n=i)=\binom{n}{i}q^i(1-q)^{n-i}.$$ We want to prove that ...


0

You say : The construction of a new set S is the union of the old set with cardinality n and an new element {a}, therefore the set that do not contain {a} still has cardinality n and the set that contains {a} is just {a}, one element... Consider the old set $S$ of cardinality $n$ whose power set has cardinality $2^n$. What is the power set of $S \cup ...


0

Here is an another, combinatorial proof. Let $X$ be a set with $n$ elements. To form a subset of $X$, we go over each element of $X$ and exercise a choice of whether or not to include in the subset. Every sequence of choices gives a different subset. Since for every element, there are 2 choices, for $n$ elements, there are $2 \times 2 \times ...$ $n$ times, ...


0

Suppose you've already shown that $X=\{1,2\}$ has $2^2=4$ subsets, namely ${\cal P}(X)=\{\emptyset,\{1\},\{2\},X\}$. Now you add a new element $a=3$ to get $Y=X\cup \{a\}=\{1,2,3\}$. The four subsets of $X$ are also subsets of $Y$, but you get new subsets - those which contain $a$, e.g. $\{1,3\}$. But each of these is one of the ones you already had ...


1

You misread the proof. Since set $X$ has $n$ elements, the induction hypothesis tells us that $|\mathcal{P}(X)| = 2^n$. The set $Y = X \cup \{a\}$ has $n + 1$ elements. It subsets are either subsets of $X$, of which there are $2^n$ by the induction hypothesis, or the union of a subset $Z$ of $X$ with $\{a\}$. By the induction hypothesis, there are $2^n$ ...


5

$$3^{2^{n+1}}-1 = (3^{2^{n}}-1)(3^{2^{n}}+1) = k2^{n+2}(3^{2^{n}}+1)$$ Now, note that $$3^{2^{n}}+1$$ is obviously even ($3^k$ is odd) and therefore divisble by $2$, and therefore we get: $$3^{2^{n+1}}-1 = 2^{n+2}\cdot 2m = 2^{n+3} \cdot m$$ Which shows that $$2^{n+3} \mid 3^{2^{n+1}}-1$$


0

How to factor the numerator: $$4n^3 + 12n^2 + 11n+3 = 4n^3 + 8n^2 + 3n + 4n^2 + 8n + 3 = n(4n^2 +8n+3) + (4n^2 +8n + 3) = (n+1)(4n^2 + 8n + 3) = (n+ 1)(2n+1)(2n+3) = (n+1)(2(n+1)-1)(2(n+1)+1)$$


0

For $n+1$ step, you don't need to expand them. $$\begin{align}\sum_{k=1}^{n+1}(2k-1)^2&=\sum_{k=1}^{n}(2k-1)^2+\{2(n+1)-1\}^2\\&=\frac{n(2n-1)(2n+1)}{3}+(2n+1)^2\\&=\frac{n(2n-1)\color{red}{(2n+1)}}{\color{red}{3}}+(2n+1)\times \color{red}{(2n+1)}\times ...


0

$$\sum_{k=1}^n (2k-1)^2 = \frac{n(2n-1)(2n+1)}{3}$$ $$\sum_{k=1}^1 (2k-1)^2=1^2 = \frac{1(2*1-1)(2*1+1)}{3}=1$$ True Assuming it is true for $k=n$: $$\sum_{k=1}^n (2k-1)^2 = \frac{n(2n-1)(2n+1)}{3}$$ Assumption of Truth Now finding for $k=n+1$: $$\begin{align}\sum_{k=1}^{n+1} (2k-1)^2&=\sum_{k=1}^n ...


2

HINT: Use $$\left\lfloor\frac{m+2}2\right\rfloor=\left\lfloor\frac m2+1\right\rfloor=\left\lfloor\frac m2\right\rfloor+1$$ In fact, $$\left\lfloor\frac mn+I\right\rfloor=\left\lfloor\frac mn\right\rfloor+I$$ for any integers $I,m,n$


0

The statement $n! = O(2^n)$ means that there is a positive $c$ and a positive integer $N$ such that $n! \le c 2^n$ for $n \ge N$, or $r(n) =\frac{n!}{2^n} \le c $ for $n \ge N$. Choosing $n \ge \max(N, 4)$, $r(n+1) =\frac{(n+1)!}{2^{n+1}} =\frac{n+1}{2}\frac{n!}{2^n} >2r(n) $. By induction, $r(n+k) > 2^k r(n) $ or $r(n) <r(n+k)/2^k < c/2^k $. ...


0

Outline: Divide $1\cdot 2\cdot 3\cdot 4\cdot 5\cdots n$ by $2\cdot 2\cdot 2\cdot 2\cdots 2$. Since $\frac{4}{2}\ge 2$ and $\frac{5}{2}\ge 2$ and so on, for $n\ge 3$ the ratio is $\ge \frac{3}{2}2^{n-3}$. If one feels like it, one can do this more formally by induction. The inequality holds at $n=3$, and the induction step is easy.


1

Hint: Stirling's approximation tells you $\log n! = n \log n - n + O(\log n)$ or that $n! \sim \sqrt{n} \left( n / e \right)^n$ where $\sim$ neglects a constant. Alternatively, assume $n! \in O(2^n)$. Then there would exists a constant $0 < k < \infty$ such that $n! \leq k 2^n$. Show something goes wrong with this for n larger than some $N$ (which is ...


0

$$\text {Suppose it is valid for n, then you can multiply by }\ (1+x)\text{ both sides and get:}$$ $$\ (1+x)^n(1+x)≥(1+nx)(1+x)$$ $$\ (1+x)^{(n+1)}≥1+x+nx+nx^2≥1+x+nx=(1+(n+1)x)$$ $$\text {where the last inequality comes from the fact that }\ nx^2≥0\text{ } \forall x∈\Bbb R \text { and n }∈\Bbb N $$


0

I like to think of it this way: We first show that if $P$ holds for some natural number $n$, then it also holds for $n+1$, i.e. it always works for the next natural number. Now since we also show that it holds for $n=0$, then it works for $n=1$ (because it always works for the next natural number). And since it works for $n=1$, it must again work for ...


5

The square brackets are just so you can correctly parse the expression, just like parenthesis in plain old arithmetic $2\times 3 + 4$ is ambiguous yet $(2\times 3) +4$ or $2\times (3+ 4)$ is not. You should interpret $P$ as a property of numbers, e.g. is prime, is even, has a unique prime factorisation, is a counter-example for the Goldback conjecture. ...


0

Case $n=2$: $1^2+2^2 = 5 < 2^3$, OK. Assuming that the inequality holds for a given $n\geq 2$, let us show that it holds also for the next one: $$\sum_{k=1}^{n+1}k^2 = \sum_{k=1}^{n} k^2 + (n+1)^2 < n^3 + (n+1)^2 < (n+1)^3,\tag{1}$$ because the last inequality is equivalent to: $$2n^2+n+1 > 0$$ that is trivial.


0

After proving that $n^{1/n}$ is irrational, prove the following stronger statement by induction on $r$: If $n_1, n_2, \dots, n_r$ are positive integers, $a_1, a_2, \dots, a_r$ are positive rational numbers, and $x$ is a positive irrational number, then the number $$\large \sqrt[n_r]{a_r+\sqrt[n_{r-1}]{a_{r-1}+\dots \sqrt[n_1]{a_1 + x}}} $$ is irrational.


1

Another idea: If you don't need to do this directly by induction, then you could try the following method. If a number is not divisible by 2 or by 3, then it is of the form $6k + 1$ or of the form $6k + 5$ (which, of course, you should check). So let's focus on the case where $n$ is even, say $n = 2m$. Then the first $2m$ numbers are exactly $$ 1, 5, 7, ...


0

So, after finishing the proof of the first part I noticed I forgot about the inductive hypothesis. I'm posting it anyway because there's no rule that says you can't use a non-inductive proof to show the inductive step. Pretend $a,b \in \mathbb{N}$ are coprime, and suppose $ab - a - b = ma + nb$ for some $m,n \in \mathbb{N}\cup\{0\}$ then we can say $ab = ma ...


1

HINT Let $X_n$ be the sequence of positive integers that are not divisible by 2 or 3 ordered ascending. Your base case for odd $n$ should be where $n$ is one. Ex -- $\frac{3}{2} * 1^2 - \frac{1}{2} = 1$. Then you need to show that if this holds for $n$, then it holds for $n+2$. Your base case for even $n$ should be the case where $n$ is two. Then you ...


1

For the first step: I think it is easier to see what you are doing when we proceed in the other direction. By that I mean, suppose we have $pab - pa - b = npa + mb$ for some $n, m \in \Bbb N$. We want to show that we can then find $n', m' \in \Bbb N$ such that $ab - a - b = n'a + m'b$. You reached the first equation from the second one by scaling by $p$ and ...


0

Yo know that $k<2^k$ and you want to prove $k+1<2^{k+1}$, but it's equal: $$k+1<2^{k+1}=2^k+2^k$$ By induction hipothesis you know that $k<2^k$ and on the other hand it's clear that $1 \leq 2^{k}$. If you add this inqeualities side by side you get $k+1<2^k+2^k=2^{k+1}$.


3

a hint: you need to show that $$ n + 1 < 2^{n+1}$$ observe that $$ 2^{n+1} = 2 \cdot 2^{n} = 2^n + 2^n$$ now use your induction hypothesis to estimate $2^n$. also observe that $1$ is the smallest natural number, i.e. $1 \leq n$


0

Hints: For all $n\ge 1$, $2^n>n>1$ $2^{n+1}=2\cdot 2^n=2^n+2^n>2^n+1$


3

For the inductive step: $$n+1\le 2n<2\times 2^n=2^{n+1}$$


0

It is not clear exactly what the author had in mind. I think there are a couple of possible interpretations. One possibility is that the author was implicitly using an inductive step $n \rightarrow n^2$ rather than the usual $n \rightarrow n + 1.$ This works for numbers that are of the form $b^{2^k}$ for $k \in \mathbb N$ and a suitable base case $b.$ That ...


0

When proving that there is exactly one nondiscrete Hausdorff topology on $\mathbf R^n$ that makes it a topological vector space over $\mathbf R$, the base case $n=1$ is actually the hardest case. (The same result is true with $\mathbf R$ replaced by $\mathbf C$ or any other nondiscrete complete valued field, such as the $p$-adic numbers.) I once read a ...


1

I've found that a much easier (yet equivalent for $\mathbb N$ under usual logic) way to view induction is the foundational approach. Instead of the Prove A(base) Assume A(k) Prove A(k+1) You only get one step and a proof by contradiction. Assume $\neg\forall x A(x)$ then $\exists x \neg A(x)$. Take least such $x$ and prove contradiction. The ...


3

This proof is using strong induction: suppose the statement is true for $1,2,3,\dots,n-1$, and show that this implies that it is true for $n$. Note that $\sqrt{n} < n$, so this is a valid inductive step. See also, e.g., http://www.mathblog.dk/strong-induction/ for more on strong induction.


3

Assuming this and then showing the assumption means that must follow, proves that "if this then that". The important part is the demonstration. This is the second step in the induction proof: $1. \quad P(1) \\2. \quad P(k) \implies P(k+1) \\\therefore \quad \forall k\in \mathbb Z^+ : P(k)$ You assume that the predicate holds for a general iteration in ...


0

A typical proof goes like this. Say you want to prove an assertion $A(n)$ is true. You prove that $A(0)$ is true, and then that if $A(k)$ is true, then $A(k + 1)$ must be true as well. That is, if it happens to be true for some number, then it must be true for the next. If you manage to prove this, then since it's true for $0$, it must be true for the next ...


0

Suppose you are making a mathematical argument. You assume $A$, and then from this you show $B$. Your question is, why are you allowed to assume $A$? The answer is, you may not conclude from this argument that $B$ is true. Because, as you observed, $A$ might not be true, since it was only an assumption. What you can conclude is that if $A$ is true, then ...


8

It works in the first case. If it works in the first case, then it works in the second case. If it works in the second case, then it works in the third case. If it works in the third case, then it works in the fourth case. $\ldots$ and so on. That's what mathematical induction does. But all of the statements above beginning with "if" are proved in one ...



Top 50 recent answers are included