# Tag Info

## New answers tagged induction

0

$3^n\ge n^2, n\ge2$ $3^{n+1}=3^n+3^n+3^n\ge n^2+n^2+n^2\ge n^2+2n+1=(n+1)^2$ This uses the fact that $n^2\ge 2n,n\ge 2$ which can be shown via induction as well and obviously $n^2\ge1$ for all $n\ge 2$. The case for $1$ can be shown and then use $2$ as the base case.

1

Essentially, you want to show that $$3n^2 > (n+1)^2$$ which is not so hard since $$3n^2 - (n^2 + 2n + 1) > 0 \iff 2n^2 - 2n-1 > 0$$ But $2n^2 - 2n - 1 = 2(n^2 -n) - 1 = (n^2-2) + (n^2 - 2n+1) =(n^2 -2) + (n-1)^2$, so that we have for all $n \geq 2$ that $2n^2 - 2n - 1 \geq 0$ since $(n-1)^2$ is always $\geq 0$ and $n^2 - 2$ is $\geq 0$ when $n\geq ... 0 Hint:$3n^2-(n+1)^2=2n^2-2n-1>0$for all$n>1$. 2 It's true for$n=1$. Assume it holds for$n$, i.e:$3^{3n} + 1 = k(3^n +1)$then consider $$3^{3(n+1)} +1 = 27 \cdot 3^{3n} + 1 = 27 (3^{3n} +1) - 26 = 27k(3^n +1) - 26$$ Let's get it into a more amenable form $$$$3^{3(n+1)} +1 = 9k3^{n+1} + 27k - 26 = 9k(3^{n+1}+1) + 18k - 26$$ \tag{1}$$ So we want to show that$3^{n+1} + 1$... 1 In my answer I'm assuming that you also have$0 \in A$and that$A$is a set of natural numbers. Otherwise as celtschk said in a comment your proof is invalid since it could be that$A$contains things besides natural numbers. The logical flaws in your proof are:$\def\nn{\mathbb{N}}$You claimed that$0 \in B$. This would require$0 \in A$by definition, ... 1 Since the meat of your question seems to be about how to prove this claim with induction (even though the other answers provide much shorter and easier proofs), that is how I will choose to approach. Checking base case: Here, we check that the statement is true for some starting value(s) of$n$. The statement's truth will depend only upon$n$as$l$is ... 0 Yeah if you use binomial theorem ..then $$\sum_{l=0}^{n} nC_l=^nC_0+^nC_1+^nC_2+......$$ Which is equal to $$1+ ^nC_1+^nC_2+....+^nC_n$$ That is$(1+1)^n$...taking x=1and a=1 in the expansion of$(x+a)^n$1 For a prove by induction: You can start the induction at$n=0$, which is trivial. So let$n$be greater than$0\begin{align} \sum_{k=0}^{n} \binom{n}{k} &= 1+ \sum_{k=1}^{n-1} \binom{n}{k} + 1 \\ &= 1+ \sum_{k=1}^{n-1} \left[ \binom{n-1}{k-1} + \binom{n-1}{k} \right] + 1 \\ &= 1+ \sum_{k=1}^{n-1} \binom{n-1}{k-1} + \sum_{k=1}^{n-1}\binom{... 0 The other approaches are much faster, but here is how you can proceed if you'd like to use induction: Forn=1$we get$\sum_{l=0}^n{n\choose l}={1\choose 0}+{1\choose 1}=1+1=2^1$For the induction step, use the identity $${n+1\choose l}={n\choose l}+{n\choose l-1}$$ for$1\leq l\leq n$to obtain $$\sum_{l=0}^{n+1}{n+1\choose l}={n+1\choose 0}+{n+1\... 1 If S is a set with n elements, then \binom{n}{l} is the number of subsets of S with l elements. \sum_{l=0}^{n}\binom{n}{l} is then the number of all subsets of S and this is equal to 2^{n} because the subsets of S can be put into bijection with the set of n-bit strings. 0 The binomial coefficient n\choose i is by definition, the coefficient of x^i in the expanded binomial (1+x)^n, i.e., (1+x)^n=\sum_{i=0}^n{n\choose i}x^i. Use this definition with x=1. 1 Hint \ To prove \,f_n = {\rm rhs} - {\rm lhs} > 0\, for all \,n\ge 2\, note \,f_2 > 0\, (base) and note$$\ \color{#c00}{f_{n+1}-f_n} =\, \frac{1}{n(n+1)}-\frac{1}{(n+1)^2}\, =\, \frac{1}{n(n+1)^2} \color{#c00}{> 0}$$thus \, f_n > 0 \,\Rightarrow\, \color{#c00}{f_{n+1} > f_n} > 0\ (induction step) Remark \ The ... 2 Let$$f(n) = \frac{1}{2^2} + \cdots + \frac{1}{n^2}.$$Now we want to show that$$f(n)<\frac{n-1}{n}\tag{1}$$for all integers greater than 1. A proof by induction consists of two equally important steps. In the base case we show that (1) indeed holds for n=2. In the inductive step we assume that (1) is true for some number n and use that to ... 0 We want to prove:$$ H_{n}^{(2)}\leq 2-\frac{1}{n}\tag{1} $$by induction. (1) holds for n=1, hence it is enough to prove that for every n\geq 1$$ H_{n+1}^{(2)}-H_{n}^{(2)}=\frac{1}{(n+1)^2}\leq \frac{1}{n}-\frac{1}{n+1} = \frac{1}{n(n+1)}\tag{2} $$holds, but that is trivial. In a similar way we me prove the improved inequality:$$\boxed{\forall n\... 1 The coefficients given by the formula are correct; for instance,${2}\choose{1}$$=2, so it gives you x^2+2xy+y^2. In general, {n}\choose{k}$$=$$$\frac{n!}{k!(n-k)!}$$ e.g.${2}\choose{1}$$=$$\frac{2!}{1!\cdot1!} = \frac{2}{1} = 2$$2 Assume the arithmetic progression, starting with \frac1{m_1}, contains k positive terms. Now the (uniform) term difference is$$ d = \frac{1}{m_1} - \frac{1}{m_2} \\ m_2 \geq m_1+1 \implies d \geq \frac{1}{m_1} - \frac{1}{m_1+1}=\frac{1}{m_1(m_1+1)} $$The entire sequence, which ends in a positive value \frac{1}{m_k}, consists of k-1 steps of size ... 2 It is important in this problem to understand that the maximun number k is determined by the choice of the two first integers m_1,m_2. Let m_1 and m_2=m_1+h (where h\ge 1); the common difference of the a. p. is d=\frac{-h}{m_1(m_1+h)} so we have$$u_1=\frac{1}{m_1}\\u_2=\frac{1}{m_1+h}\\u_3=\frac{1}{m_1+h}+\frac{-h}{m_1(m_1+h)}=\frac{m_1-h}{m_1(...

2

Since they are in arithmetic progression let us call $1/m_n-1/m_{n+1}=L>0$. We then have that \begin{align} \sum_{n=1}^{k-1}\left(\frac{1}{m_n}-\frac{1}{m_{n+1}}\right) &= \sum_{n=1}^{k-1}L \\ &= (k-1)L \\ &= \frac{1}{m_1}-\frac{1}{m_k} \end{align} Which means we just have to show k=\frac{\frac{1}{m_1}-\frac{1}{m_k}}{L}+1<m_1+2\qquad (... 0 Let S be the set of all permutations f of {1,2,3,..,, n+1} with at least one non-fixed point (i.e., a value k with f(k)≠k). Then |S| = (n+1)!-1. Now count the permutations with the highest non-fixed point first, then those with the 2nd highest non-fixed point (which are not already counted), then those with the 3rd highest non-fixed point (which ... 0 Here is how I would write up the main part of the induction proof (DeepSea and Bill handle the base case easily), in the event that you may find it useful: \begin{align} a^{4k+5}-a&= a^4(a^{4k+1}-a)+a^5-a\tag{rearrange}\\[1em] &= a^4(30\eta)+a^5-a\tag{by ind. hyp.; \eta\in\mathbb{Z}}\\[1em] &= a^4(30\eta)+30\ell\tag{by base case; \ell\in\... 0 The induction hypothesis is that a^{4n+1}-a=30k, for some integer k. Therefore a^{4(n+1)+1}-a=a^4\cdot a^{4n+1}-a=a^4(30k+a)-a=30ka^4+a^5-a $$and the proof is reduced to showing that a^5-a is divisible by 30, which is the base step. 0 Hint \  See this answer for various proofs of the base case \,30\mid \color{#0a0}{a^{\large 5}-a}.\, The inductive step is {\rm mod}\ 30\!:\,\ \color{#c00}{a^{\large 4n+1}\equiv a}\,\Rightarrow\,a^{\large 4(n+1)+1}\!\equiv a^{\large 4} \color{#c00}{a^{\large 4n+1}}\!\equiv a^{\large 4}\color{#c00}a\equiv \color{#0a0}{a^{\large 5}\equiv a}.\ \  QED ... 0 Don't factor entirely. Just factor enough to realize a^{4n+1} - a = a(a^{4n} - 1)=a(a - 1)(a^{4n-1} + a^{4n-2} + .... + a + 1). Assume for n = k that a^{4k + 1}-a= a(a^{4n} - 1)=a(a - 1)(a^{4k-1} + a^{4k-2} + .... + a + 1)= 30M then a^{4(k+1) + 1} - a = a(a-1)(a^{4k + 3} + ...)= a(a-1)(a^{4k + 3} + a^{4k + 2} + a^{4k+1} + a^{4k}) +a(a - 1)(a^{... 0 a(a^{4n}-1)=a(a^{2n}-1)(a^{2n}+1)=a(a^{n}-1)(a^{n}+1)(a^{2n}+1). Assume 30 | a(a^{4n}-1). 30 | a(a^{4(n+1)}-1) if and only if 30 | a(a^{4(n+1)}-1)-a(a^{4n}-1). Try factoring: a(a^{4(n+1)}-1)-a(a^{4n}-1). Think about how regardless of a, you can show that one of the terms of the factorization must be divisible by 2, another divisible by 3, and ... 1 We start with the base case: n = 1 \implies P(1): a^5 - a = a(a-1)(a+1)(a^2+1). The product  6 = 3! \mid a(a-1)(a+1) . If a = 0, 1, 4 \pmod 5 \implies 5 \mid a^5 - a \implies 30 \mid a^5 - a since \text{gcd}(5,6) = 1. If a = 2, 3 \pmod 5 \implies 5 \mid a^2 + 1 \implies 30 \mid a^5 - a. Thus P(1) is true. Assume P(n): 30 \mid a^{4n+1} - a is ... 9 As an interesting alternative, note that x^3 +1 = (x+1)(x^2 - x + 1), so setting x = 3^n gives 3^{3n} + 1 = (3^n + 1)(3^{2n} - 3^n + 1). 2 Divide both sides by 2, and you have the fact that the sum up to n+1 of  \left( \begin{array}{c} k \\ 2 \end{array} \right)  is  \left( \begin{array}{c} n+2 \\ 3 \end{array} \right) . This is the reason that the total number of gifts given in The Twelve Days of Christmas song is  \left( \begin{array}{c} 14 \\ 3 \end{array} \right) =364 . In ... 2 You have proved the statement via induction. Your job is done. When you write that$$\sum_\limits{k}^{n+1}k(k+1)=\frac{1}{3}(n+1)(n+2)(n+3)$$What you actually mean is$$\sum_\limits{k}^{n+1}k(k+1)=\frac{1}{3}(n+1)\{(n+1)+1\}\{(n+2)+1\}$$So if I represent the mathematical statement \sum_\limits{k}^{n}k(k+1)=\frac{1}{3}n(n+1)(n+2) as P(n), then you ... 0 You have actually proved the statement, but it is a little hard to see, because in your inductive step you went from n to n+1. Instead, go from n-1 to n: Suppose the statement holds for n-1, so$$ S_{n-1} := \sum_{k=1}^{n-1} k (k+1) = {1 \over 3} (n-1) (n) (n+1). $$Then$$ S_{n-1} + n(n+1) = n (n+1) \left[ 1 + {1 \over 3} (n-1) \right] = n (n+...

2

You already have the first step, that it is true for $n=1$. In the second step, you are assuming it is true for $n$ and you want to prove it is true for $n+1$. So by assumption your $\sum_{k=1}^{n} k(k+1)$ is $\frac{1}{3} n (n+1)(n+2)$, and you want to show that $$(n+1)(n+2) + \frac{1}{3} n (n+1)(n+2) = \frac{1}{3} (n+1)(n+2)(n+3)$$ which is a ...

0

You have proven that it is true for the case that n = 1 (i.e. that 2 = 2 - this is called the base case). You have then shown that if the relationship is true for n, it is also true for n + 1 (this is the inductive case); this is what the last line shows. Therefore, since it is true for n = 1, it is true for n + 1 = 2; since it is true for n = 2, it is true ...

1

Hint : For $k^2 \le p < (k+1)^2$, we have $k=\sqrt{k^2} \le \sqrt{p} < \sqrt{(k+1)^2}= k+1$. So using the definition of the floor function, what could be the value of $\lfloor \sqrt{p} \rfloor$?

0

Show the contrapositive: If we have more tan $2^{n-1}$ subsets, then we find two among them that are disjoint. This can be done by the pigeon-hole principle: There are exactly $2^{n-1}$ subsets $A$ with $n\notin A$. If declare $A$ and $\{1,2,,\ldots,n\}\setminus A$ as a "hole", then we have $2^{n-1}$ holes. Henec if we have more than $2^{n-1}$ subsets - or "...

2

Note that there are exactly $2^n$ subsets in total to choose from. It is easy to see how to pick $2^{n-1}$ pairwise intersecting sets because we can just take all subsets of $[n-1]$ and then add $n$ to them. To see that we cannot have more than $2^{n-1}$ pairwise intersecting sets, begin with a set of $2^{n-1}$ pairwise intersecting sets. For each of those ...

2

An inductive proof is not the way to go. HINT: Let $[n]=\{1,\ldots,n\}$. If $A\subseteq[n]$, can such a collection contain both $A$ and $[n]\setminus A$? What I think you’re missing in your attempt to prove the result by induction is that there are many such collections of subsets of $[n]$. For instance, if $n=3$ one such collection is $$\big\{\{1\},\{... 1 Note: An inductive proof is given as an answer by David W.Farlow. Explanations of some steps and flaws in your inductive argument: We get (1) from the inductive hypothesis (which is assumed to be true.)$$(1+kh) \leq (1+h)^k \Rightarrow (1+h)(1+kh) \leq (1+h)^k(1+h)=(1+h)^{k+1}$$as h >-1 \Rightarrow h+1>0 and so multiplication of both sides ... 0 First of all, why have you been reading a bunch of solutions? I suggest you make a serious attempt at the problem yourself and only then look to other solutions to bridge whatever gap that exists in your reasoning (looking up a solution should be the very last resort). To that end, note that the inequality is trivial for when n=0,1. Thus, consider the ... 1 The induction step breaks down to: Let X = \cup_{i=0}^n A_i; a union of n finite sets that is, by assumption finite. Let Y = A_{n+1}; a finite set. So \cup_{i=0}^{n+1} A_i = X \cup Y; the union of two finite sets. Suffices to show the union of two finite sets is finite. Which is so absolutely obvious we just know it's going to be a bitch to ... 1 By definition,$$\bigcup\limits_{i=1}^{k+1} A_i = [\bigcup\limits_{i=1}^k A_i] \cup A_{k+1}$$Since p(k) is true, \bigcup\limits_{i=1}^k A_i is finite. Since p(2) is true (i.e. the union of two finite sets is finite), so is p(k+1). I want to point out that if A_1, ... , A_n are sets, \bigcup\limits_{i=1}^n A_i doesn't necessarily make sense. ... 1 I'm not sure what you mean by multiplying or adding anything. You need to show that$$\bigcup_{i=1}^{k+1}A_i$$is finite. In particular$$\bigcup_{i=1}^{k+1}A_i=\left(\bigcup_{i=1}^{k}A_i\right)\bigcup A_{k+1}$$and thus you have the union of two finite sets. Depending on your definition of finite, this may be all you have to say (i.e. the union of two ... 0 We give some hints for your question: 1) S_{n+1}-S_n=x^n 2) \displaystyle\frac{x^{n+1}-1}{x-1}-\displaystyle\frac{x^{n}-1}{x-1}=x^n. 0 Let S(n) be the statement: \displaystyle\sum_{k=0}^{n-1}x^{k}=\dfrac{x^{n}-1}{x-1} Basis step: S(1): LHS: \displaystyle\sum_{k=0}^{(1)-1}x^{k}=x^{0} \hspace{23 mm}=1 RHS: \dfrac{x^{(1)}-1}{x-1}=\dfrac{x-1}{x-1} \hspace{27 mm}=1 \hspace{73.5 mm} LHS = RHS \hspace{1 mm} (verified.) Inductive step: Assume S(m) is true, i.e. assume ... 0 Another approach is to use congruences: First note that if k is odd, then$$ 4^k\equiv 4\ (\text{mod}\,10). $$Now, if n is odd, then n+2 is odd, so$$ 1^{n+2}+2^{n+2}+3^{n+2}+4^{n+2}\equiv 1+2^{n+2}+3^{n+2}+4=5+2^{n+2}+3^{n+2}\ (\text{mod}\,10). $$It suffices to prove that 5\mid 2^{n+2}+3^{n+2}. Indeed, since n+2 is odd we get$$ 2^{n+2}+3^{n+2}\...

3

Induction: Consider the difference, $$\left(1 + 2^{n+2} + 3^{n+2} + 4^{n+2}\right)-\left(1+2^n+3^n+4^n\right).$$ Is it divisible by $10$?

2

You made lots of little mistakes but your biggest mistake is that you inductions step, doesn't actually do any inducing. A proper induction step always goes like this: ======= We assume that something is true for a specific $k = n$ $\implies$ Then something is true for $k = n+1$. ====== Thus, we start with showing it is true for $k=$ base case; thus ...

0

We can also use the Abel's summation and get $$S=\sum_{k=1}^{n}\frac{1}{\sqrt{k}}=\sum_{k=1}^{n}1\cdot\frac{1}{\sqrt{k}}=\sqrt{n}+\frac{1}{2}\int_{1}^{n}\frac{\left\lfloor t\right\rfloor }{t^{3/2}}dt$$ where $\left\lfloor t\right\rfloor$ is the floor function. Since $t-1\leq\left\lfloor t\right\rfloor \leq t$ we have 2\sqrt{n}-2+\frac{1}{\sqrt{...

2

Hint  Equivalently we seek to prove that $\,f(n) = 2^n/(4n) > 1\,$ for all $\,n\ge 5.$ Note $\,f(5)>1\,$ and $\,f(n\!+\!1)/f(n) = 2n/(n\!+\!1) \ge 1\,$ for $\,n\ge 5\,$ so $\,\color{#c00}{f(n\!+\!1) \ge f(n)}\,$ Hence the induction reduces to a trivial one:  an $\rm\color{#c00}{increasing}$ sequence stays $\,\ge\,$ its initial value. From ...

3

You got the basis step correct by checking that $4n<2^n$ for $n=5$. Next, you must prove that $4N<2^N \implies 4(N+1) < 2^{N+1}$ for $N\geq5$ When trying to solve this problem, simplify the right-hand-side of this implication to a form that is easily comparable to the left-hand-side. Notice that $4(N+1) < 2^{N+1}$ holds if and only if 4N+4 &... 4 Consider the following (see if you can determine how one step relates to another): \begin{align} 4(k+1)&=4k+4\\[1em] &< 2^k+4\tag{why?}\\[1em] &< 2^k+2^k\tag{why?}\\[1em] &= 2\cdot2^k\\[1em] &=2^{k+1}. \end{align} 1 Your choice ofn$should only be for the basis of the induction, not for the inductive step. What you need to do is to show that if$4n<2^n$then$4(n+1)<2^{n+1}$. One way of doing that is to say that$4(n+1)=4n+4<2^n+4$and then argue that$x+4<2x\$ for the relevant values.

Top 50 recent answers are included