# Tag Info

0

Hint: $$(k+1)!> (k+1)^2$$ can be rewritten as $$(k+1)\cdot (k!) > (k+1)\cdot(k+1)$$

0

As others have commented, the problem as stated is (twice) incorrect, since $x_1 = 1$ and $x_2 = 5/7 < 1$, and it is therefore impossible to give an answer as is. However, it is possible to make a complete study of the sequence $x_n$ in the following way: it is easy to see that if we define two sequences $y_n, z_n$ by $$y_1 = x_1, z_1 = 1, \quad y_{n+1} ... 1 First, show that this is true for n=1: \sum\limits_{k=1}^{1}k\cdot{k!}=(1+1)!-1 Second, assume that this is true for n: \sum\limits_{k=1}^{n}k\cdot{k!}=(n+1)!-1 Third, prove that this is true for n+1: \sum\limits_{k=1}^{n+1}k\cdot{k!}= \color{red}{\sum\limits_{k=1}^{n}k\cdot{k!}}+(n+1)\cdot(n+1)!= ... 1 Well we know that (k+2)! = (k+2)\times(k+1)\times k \times (k-1) ... \times 1. However, we know that this can be expressed as (k+2)(k+1)! And so you don't even need to do anything else. You are basically done. Here is the general formula. (k+p)! = (k+p)(k+p-1)! and (k+p-1)! = (k+p-1)(k+p-2)! and so on 1$$(k+1)!-1+(k+1)(k+1)! ==(k+1)!+(k+1)(k+1)! -1==(k+1)![1+(k+1)] -1==(k+1)![k+2] -1=(k+2)!-1$$0 Hints: i)$$\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}~\forall~1\leq k\leq n$$ii)$$\binom{n+1}{0}=\binom{n}{0}~\forall~n\in\Bbb{N}$$Use these two hints to approach both the problems. 0 A proposal for case 1 (simple induction): Here are some generic recommendations for beginners I have given in previous answers (here or here): Write down in full length the statement P_n to be proven at rank n, and the range of values n over which P_n should stand Clearly mark the anchors of the induction proof: base case, inductive step, ... 2 Try to derive the statement for k+1 using the truth of the statement for k: Have a new guest, the (k+1)-st guest arrive and shake everyone else's hand, after all the other k guests have shaken hands with each other. This last guest will shake hands with the remaining k people, so that the total number of handshakes is the number of shakes between ... 1 First note that gcd(p^n,r) for r=\overline{1,p^n} must be of the form p^k with k\in\overline{0,n}, and for each k there is exactly \phi(p^{n-k}) numbers with that property in \overline{1,p^n} so:$$\sum_{r=1}^{p^n} \frac{p^n}{gcd(p^n,r)} = \sum_{k=0}^{n} \frac{p^n}{p^k}\phi(p^{n-k}) = 1+\sum_{k=0}^{n-1} \frac{p^n}{p^k}p^{n-k}(1-\frac{1}{p}) = ...

0

Jensens inequality for the convex function $f(x)=x^{-n}$ tells us that $$\left(\frac{a+b}2\right)^{-n}=f\left(\frac{a+b}2\right)\le\frac{f(a)+f(b)}2=\frac{a^{-n}+b^{-n}}2$$ which transforms to $$\frac{2^{n+1}}{(a+b)^n}\le\frac1{a^n}+\frac1{b^n}$$ Hence you only need to show that $2n\le 2^{n+1}$. If you can't use Jensens inequality or the chain of mean ...

1

What's being cascaded is not induction but, rather, telescopy (to essentially construct the difference operator / recurrence that annihilates $\,f_n = S_n).\$ The telescopic step is this. Theorem $\ \ m\mid f_n= a^n\! + g_n\,$ for all $\,n\iff m\mid g_{n+1}\!-ag_n\,$ for all $\,n,\,$ and $\,m\mid f_0$ Proof $\ (\Rightarrow)\ \ f_{n+1}\!-af_n = ... 1 The constant difference between each term is not$b$, and the first term is not$1$(but rather$a+b$). For clarity, I would recommend doing the following. Split the sum into two parts: $$\sum_{i=1}^n ai + \sum_{i=1}^n b$$ This is equivalent to: $$[a + 2a + 3a + \dots + (n-1)a + na] + [b + b + b + \dots + b +b]$$ The first sum is an arithmetic ... 1 At first sight it seems to be false because 1/n tends to 0. But I trust you so your inequality is nice. Want I want to remark is you have at hand a pretty proof that the harmonic series is divergent (You have an infinity of "packages" each of them greater than 13/24) 1 We want to show that, given the inductive hypothesis, $$(k+1)^2 =\sum_{i=1} ^{k+1} (2i-1)$$ LHS:$k^2 + 2k+1$. The RHS$\begin{align} \sum_{i=1} ^{k+1} (2i-1)& \overset{IH}{=} k^2 + 2(k+1) - 1 \\ & = k^2 + 2k +2-1 \\ \\ & = k^2 + 2k + 1\end{align}$Hence, given the inductive hypothesis, it follows that$(k+1)^2 =\sum_{i=1} ^{k+1} (2i-1)$. ... 6 You haven't done anything wrong. The thing is, what you have done is just check one possible approach to proving the result, and found that it doesn't work. Where you said so basically I have to prove that it would have been a bit more precise to say so it would be enough to prove that That was correct — it would be enough — but unfortunately, ... 6 As I see it, here's what might be confusing you: If you let $$A=\frac{1}{n}+\frac{1}{n+1}+\frac{1}{n+2}+\dots+\frac{1}{2n}+\frac{1}{2n+1}+\frac{1}{2n+2},$$ and $$B=\frac{13}{24}+\frac{1}{n},$$ then you are trying to prove that$A>B$. Also, if you let $$C=\frac{13}{24}+\frac{1}{2n+1}+\frac{1}{2n+2},$$ then you have by assumption that$A>C$. Thus ... 2 Let $$A_n = \frac{1}{n}+\frac{1}{n+1}+\ldots+\frac{1}{2n}=H_{2n}-H_{n-1}.\tag{1}$$ Then: $$A_n-A_{n+1} = \frac{1}{n}-\frac{1}{2n+1}-\frac{1}{2n+2}>0 \tag{2}$$ hence the sequence$\{A_n\}is decreasing and to prove our claim it is enough to show that: $$\lim_{n\to +\infty}A_n >\frac{13}{24}=0.541666\ldots.\tag{3}$$ However, by a Riemann sum ... 0 Meat of induction step: \begin{align} \sum_{i=1}^{k+1}\frac{1}{i^2} &= \frac{1}{(k+1)^2}+\sum_{i=1}^k\frac{1}{i^2}\\[1em] &< \frac{1}{(k+1)^2}+2-\frac{1}{k}\tag{by ind. hyp}\\[1em] &= 2-\frac{1}{k+1}\left(\frac{k+1}{k}-\frac{1}{k+1}\right)\\[1em] &= 2-\frac{1}{k+1}\left(\frac{k^2-k}{k(k+1)}\right)\\[1em] &< 2-\frac{1}{k+1}\tag{since ... 1 For inductive step : \begin{align}\sum_{k=1}^{n+1}\frac{1}{k^2}&=\color{red}{\sum_{k=1}^{n}\frac{1}{k^2}}+\frac{1}{(n+1)^2}\\&\lt\color{red}{2-\frac 1n}+\frac{1}{(n+1)^2}\\&=2-\frac{(n+1)^2-n}{n(n+1)^2}\\&=2-\frac{1}{n+1}\left(\frac{n^2+n+1}{n(n+1)}\right)\\&=2-\frac{1}{n+1}\left(1+\frac{1}{n(n+1)}\right)\\&\lt ... 1 By induction assume it is true for n. Then, by induction, \sum_{k = 1}^{n+1} \frac{1}{k^{2}} =\sum_{k = 1}^{n} \frac{1}{k^{2}} +\frac{1}{(n+1)^2} < 2-\frac{1}{n} +\frac{1}{(n+1)^2}. So to finish we need 2-\frac{1}{n} +\frac{1}{(n+1)^2} \leq 2 - \frac{1}{n+1}, or \frac{1}{n+1} \leq \frac{1}{n}-\frac{1}{(n+1)^2}, which is true for n>1. 0 Your summations following the question are not correct: they should be\begin{align*} \sum_{k=1}^1\frac{k}{(k+1)!}&=\frac1{(1+1)!}=\frac12\\ \sum_{k=1}^2\frac{k}{(k+1)!}&=\frac1{(1+1)!}+\frac2{(2+1)!}=\frac12+\frac26=\frac56\\ \sum_{k=1}^3\frac{k}{(k+1)!}&=\frac56+\frac3{(3+1)!}=\frac56+\frac3{24}=\frac{23}{24}\\ ... 0 The proof can be organized with strong induction, which is equivalent to normal induction but sometimes gives a clearer proof. First, the base casen=1$is$1\cdot 2^0$, a product of an odd number and a power of two. Second, let$n>1$and assume that the statement holds for all$1\leq m<n$. If$n$is odd, then$n=n\cdot 2^0$. If$n$is even, say ... 0 Well for even numbers. You will set$p=0$and you basically keep incrementing the$k$by 1 in C++ notation its$k++$and in mathematics notation it's$k+1$and so Given that$2k+1$is odd , it's very obvious that$2(k+1)+1 = 2k+3$is odd and on the other hand for odd numbers , you set$k=0$and then you increment your$p$and it's also obvious that if$2^p$... 1 Non-inductive proof:$n^3+(n+1)^3+(n+2)^3=3\underbrace{(n-1)n(n+1)}_{3\text{ consecutive integers}}+\underbrace{9(n^2+2n+1)}_{\text{divisible by }9}$Three consecutive integers must have one of them divisible by$3$. You wrote$\frac{(k+1)^3 + ((k+1)+2)^3 + ((k+1)+3)^3}{9}=\frac{(k+1)(1+2+3)^3}{9}$, which is incorrect. Also then you wrote$1+2+3=9$. ... 0 Hint: Recall that$(a+b)^3=a^3+3a^2b+3ab^2+b^3$. Expand$(k+1)^3 + ((k+1)+1)^3 + ((k+1)+2)^3$to get $$(k^3+(k+1)^3+(k+2)^3)+\text{something}$$ Study that something. 2 For$n,m\in\mathbb{Z}$and$n>m>1$, we can use the identity $$F_{n-m+1}F_m+F_{n-m}F_{m-1}=F_n\tag{1}$$ to prove that for any$n,m\in\mathbb{Z^+}$that$F_m$divides$F_{nm}$(i.e.,$F_{nm}$is a multiple of$F_m$). To accomplish this, fix$m\geq 1$and induct on$n$. For each$n\geq 1$, let$S(n)$denote the statement that$F_m$divides$F_{mn}$. ... 5 In fact your formula can be written: $$F_{n+k+1} = F_{k+1}F_{n+1} + F_{k}F_{n}$$ and this is symmetric on$k$and$n$so the same argument works also, (you can only change$k$on$n$and$n$on$k$and your first proof becomes an induction on$n) 0 suppose that \begin{align} S_n&=&\sum_{i=0}^{n-1}(2i+1)\\ &=&\sum_{i=0}^{n-1}i+(i+1)\\ &=&\sum_{i=0}^{n-1}i + \sum_{i=0}^{n-1}(i+1)\\ &=&\sum_{i=1}^{n-1}i + \sum_{i=1}^{n}i\\ &=&t_n+t_{n-1}\\ \end{align} where $$t_n=\frac{n(n+1)}{2}$$ so $$S_n = ... 3 It may help you to realize that$$ 1+5+9+\cdots+(4n+1) = (n+1)(2n+1) $$may actually be rewritten as$$ \sum_{i=0}^n(4i+1)=(n+1)(2n+1). $$Thus, for n\geq 0, let S(n) denote the statement$$ S(n) : \sum_{i=0}^n(4i+1)=(n+1)(2n+1). $$Base case (n=0): S(0) says that 4(0)+1=1=(0+1)(2(0)+1), and this is true. Induction step: Fix some k\geq 0 and ... 2 No, it's fine. For n = 1, the last term is 4n + 1 = 5, so the LHS is just 1 + 5 = 6, which matches the RHS. In fact, you could even start your base case at n = 0. 0 Since 2187=3^{7}<7!=5040 then for n>7$$ 3^{n}=3^{7}\cdot3^{n-7}<7!\cdot8\cdot9\cdot\ldots\cdot n=n! $$since 8,9,\dots n>3 5 We can prove it by induction. For n\geq 7, let S(n) denote the statement$$ S(n) : 3^n < n!. $$Base case (n=7): S(7) says that 3^7 = 2187<5040=7!, and this is true. Induction step: Fix some k\geq 7, and assume that S(k) is true where$$ S(k) : 3^k < k! $$To be shown is that S(k+1) is true where$$ S(k+1) : 3^{k+1} < (k+1)! $$... 2 I'm trying to learn mathematical induction. This is a notoriously difficult proof technique for people to understand when encountering it for the first time; however, there seem to be a few conceptual misunderstandings wrapped into your question that make it seem like your question is more about reindexing the sum than actually about constructing a ... 3 Set k=n-1 so you have$$\sum_{i=0}^k(2i+1)=(k+1)^2$$When k=0 you have the base case 2\times 0+1=1 and everything works fine. You will have proved the identity for k\ge 0 which is equivalent to n\ge 1. This method, with k=n-r, turns the induction from n=r to a "technically correct" induction from k=0, and when proved as a theorem justifies ... 1 If I understand your question, try replacing n by (n+1) in your formula$$\sum_{i=0}^{n} (2i+1)=(n+1)^2\qquad\text{(1)}$$Then if n equals som number k we have$$ \sum_{i=0}^{k} (2i+1)=(k+1)^2\qquad\text{(2)} $$By testing equation (2) for k=0$$\sum_{i=0}^{0} (2i+1)=(0+1)^2\implies1=1$$we assume that equation (1) holds for n=k and proceed ... 0 HINT Take U_n=\sqrt{1+\sqrt{2+ ... + \sqrt{n}}} Then show that \forall n \in \mathbb{N}, U_{n+1}^2 < 1+\sqrt{2} U_n After than consider Q(x)=x^2-\sqrt{x}-1 find his solutions then consider Q(U_n) if it works you will find that$$ \lim_{n \to \infty} U_n \le \frac{\sqrt{2}+\sqrt{6}}{2} <3 $$8 We can actually prove a more general version of what you hope to prove (set a=0 for your problem, specifically): Claim: For every n\in\mathbb{Z^+} and every non-negative real number a$$ \sqrt{a+1+\sqrt{a+2+\cdots+\sqrt{a+n}}}< a+3. $$Proof. For n\geq 1, let S(n) denote the statement that for any non-negative real a,$$ S(n) : ... 2 You can also try going at it from the other direction: by squaring both sides, the given inequality can be written as1+\sqrt{2+\sqrt{3+\ldots}}\lt 3^2$. Subtract$1$and square:$2+\sqrt{3+\ldots}\lt (3^2-1)^2$. Subtract 2 and square:$3+\sqrt{\ldots}\lt\left((3^2-1)^2-2\right)^2$. So define$a_0=3$,$a_i=a_{i-1}^2-i$. Can you show by induction that ... 5 $$(1) \quad x=k+\sqrt x$$ $$x=\sqrt {k+\sqrt x}$$ continuing the recursion... $$x=\sqrt {k+\sqrt {k+\sqrt {k+...}}}$$ Thus (1) is the equivalent expression. Solve for x with$k=1$$x=\phi$$ Thus, x equals the golden ratio. Multiply the expression by c... $$c \cdot x=c \cdot \sqrt {k+\sqrt {k+\sqrt {k+...}}}$$ $$c \cdot x=\sqrt {c^2 \cdot k+\sqrt {c^4 \cdot ... 1 Take the statement as:$$P(n):\sum_{k=0}^n2^k=2^{n+1}-1$$Base case (k=0): ~~P(0): \textrm{LHS}=\displaystyle\sum_{k=0}^02^k=2^0=1=2-1=2^{0+1}-1=\textrm{RHS} Assumed case (k=n):$$P(n):\sum_{k=0}^n2^k=2^{n+1}-1\tag1$$Inductive step (k=n+1):$$\begin{align}\textrm{LHS}=\sum_{k=0}^{n+1}2^k ... 0 Have a look at my previous answers to induction-related questions : Solution verification: Prove by induction thata_1 = \sqrt{2} , a_{n+1} = \sqrt{2 + a_n} $is increasing and bounded by$2$Proof by Induction: There are some methodological hints that could help you. 3 The base case is when$n=2$and it is called Euclid's lemma. To see how you can prove the result via induction we shall do it over$n$(The number of factors). Suppose that you have proved it for$n$factors and wish to prove it for$n+1$. We must prove that if$p|a_1a_2\dots a_{n+1}$then$p$divides one of the$a_j$'s. Notice that$p|(a_1a_2\dots ...

5

It is a mixture of all of them. You can try the following approach: let $$S_n = \sum_{k=0}^{n}(2k+1)3^k.$$ Then: $$S_{n+1}-3\,S_n = \sum_{k=0}^{n+1}(2k+1)3^k-\sum_{k=1}^{n+1}(2k-1)3^k = 1+2\sum_{k=1}^{n+1}3^k=3^{n+2}-2$$ and: $$S_n = (S_n-3S_{n-1})+3(S_{n-1}-3S_{n-2})+9(S_{n-2}-3S_{n-3})+\ldots$$ leads to: $$S_n=\sum_{k=0}^{n}(2k+1)\,3^k = n ... 0 Exactly, so the answers are : (1) Sum (i=0 to n) 3^n = (3^(n+1)-1)/2 (2) Sum (i=0 to n) n*3^n = 3*(2*n*3^n-3^n+1)/4 3 The sum is given by$$\sum_{k=1}^{n+1} (2k-1)3^{k-1} = 2\sum_{k=1}^{n+1} k \cdot 3^{k-1} - \sum_{k=1}^{n+1} 3^{k-1}$$Recall that$$\sum_{k=1}^{n+1} x^k = \dfrac{x(x^{n+1}-1)}{x-1}$$and$$\sum_{k=1}^{n+1} k \cdot x^{k-1} = \dfrac{(n+1)x^{n+2}-(n+2)x^{n+1}+1}{(x-1)^2}$$I trust you can now finish it off. 0 Assume that it is true for n-1, i.e. I_{n-1} < (n-1)!, then I_n < nI_{n-1} < n\cdot (n-1)! = n!, and it is therefore true for all n. 3 HINT: Let P be the set of positions described in the question:$$P=\{\langle 0,0\rangle\}\cup\{\langle 2n,2n-1\rangle:n\in\Bbb Z^+\}\;.Show that if \langle m,n\rangle\notin P, the person whose turn it is to move can always move to a position in P. Show that if \langle m,n\rangle\in P, every possible move will leave a position that is not in ... 1 To prove 2^{k+2} > (k+1)^2. Consider the left side \begin{align*} 2^{k+2} & = 2^{k+1} \, . 2\\ & > k^2 \, . 2 && (\text{by induction hypothesis})\\ & = k^2+k^2\\ & > k^2 + (2k+1) && (\text{for all } k \geq 3, k^2>2k+1)\\ & = (k+1)^2. \end{align*} So you need to adjust your base stpes to cover the missing ... 0 By cross-multiplying, it can easily be seen that \begin{align} \frac{\sqrt{k+1}}{2k} &\gt\frac1{\sqrt{k+1}+\sqrt{k\,}}\\[6pt] &=\sqrt{k+1}-\sqrt{k\,} \end{align} $$Summing gives$$ \sum_{k=1}^n\frac{\sqrt{k+1}}{2k} \gt\sqrt{n+1}-1  This is not the inequality given, but for $n\ge2$, $\sqrt{n+1}-1\gt\frac{\sqrt{n}}2$.

3

This is an interesting, and rather unfortunate, problem in a way because the answer really depends on how you interpret the question (and, of course, ambiguity is not exactly something desired in mathematics). The two possible interpretations: In the proof just given (i.e., the one in your picture), why do you need the two base cases $n=0$ and $n=1$? Or: ...

Top 50 recent answers are included