# Tag Info

0

For n=3, $4^2+4^3=\frac{4^2(4^2-1)}{3}$ Now for any n=k, assume that, $4^2 + 4^3 + 4^4 + · · · + 4^k = \frac{4^2(4^{k-1} -1)}{3}$ Now, it has to be true for k+1, $4^2+4^3+...+4^k+4^{k+1}=\frac{4^2(4^k-1)}{3}$ $\frac{4^2(4^{k-1} -1)}{3}+4^{k+1}=\frac{4^2(4^k-1)}{3}$ $3.4^{k+1}=4^2(4^k-1-4^{k-1}+1)$ Observe that both sides have been multiplied by $3$ ...

0

But this is the well known formula for geometric sequence. $a_1, a_1q, a_1q^2, \ldots, a_1q^{n-2}=a_1\frac{q^{n-1}-1}{q-1}$ with $a_1=4^2$ and $q=4$.

0

Hint. For the inductive step, you need to prove that $$\frac{4^2(4^{n-1} -1)}{3}+4^{n+1}=\frac{4^2(4^n -1)}{3}\ .$$

1

What Daniel Fischer, Brian Tung, Michael Hardy, and myself now are referring to is that the empty sum is taken to be zero; on the other hand, the empty product is taken to be one. More concretely, $$\sum_{i=r}^k\Omega_i=0\quad\text{when}\quad k<r\quad\text{and}\quad\prod_{i=r}^k\Omega_i=1\quad\text{when}\quad k<r.$$ Now, consider Brian's comment; ...

1

As the comments have indicated, the equation is actually valid for $n = 1$, after a fashion. It is clearer when written as a summation: $$\sum_{k=2}^n (5k-4) = \frac{n(5n-3)-2}{2}$$ Spelled out in words, the above equation reads, "The sum of $(5k-4)$, from $k = 2$ to $n$, equals $\ldots$" When $n = 1$, the summation on the left is empty, and an empty ...

0

Core part of induction step: \begin{align} \sum_{r=1}^{k+1}(6r-2) &= [6(k+1)-2]+\sum_{r=1}^k(6k-2)\tag{by defn. of $\Sigma$}\\[0.5em] &= 6k+6-2+k(3k+1)\tag{by ind. hyp.}\\[0.5em] &= 3k^2+7k+4\tag{simplify}\\[0.5em] &= (k+1)(3k+4)\tag{factor} \end{align}

0

$3k^2 + k + 6k + 6 - 2$ Hint: $(3k^2 + 6k + 3) + (k + 1)$

0

Tip: Prove that $10^{n-1}$ is the smallest $n$ digit decimal number. Then prove that $10^{n}-1$ must be the largest $n$ digit decimal number, because $10^n$ is the smallest $n+1$ digit number.

1

Given a decomposition of $a$ into digits as $a=\sum_{i=0}^{n-1}a_i10^i$ such that $a_{n-1}\ne0$ and each $a_i$ satisfies $0\le a_i<10$, we say that $a$ is an $n$-digit number (in base 10). Under these circumstances, we want to show: An $n$-digit number $a$ satisfies $10^{n-1}\le a<10^n$. For the lower inequality, use the lower bounds $0\le a_i$ ...

3

Another alternative way to show it is to consider the following. $f(x)=\frac{2x^2 +4x-2}{2x+3}$ Then you find the derivative with respect to x. You see for every $x>0$ the derivative is positive therefore the function is increasing. Therefore $x1<f(x1)=x2<f(f(x1))=x3<...$ and so on.

8

Rewriting $x_{k+1}$ (and given that $x_k>2$) we have $$x_{k+1}=\frac{2x_k^2 +4x_k -2}{2x_k+3}=x_k+\frac{x_k-2}{2x_k+3}>x_k>2$$

0

Trivial 'strong' induction. $f(n):\space n$ is sum of $4s$ and $5s$ $1)$base cases:$12/n_0,13,14,15,16/n_1$ $2)f(n)$ $3)f(n-4)\space\space 2)$ $4)(n-4)+5=n+1$ $5)f(n+1)\space\space 3),4)$ $6)f(n-4)\rightarrow f(n+1)\space\space 5)$ $7)f(n),n\ge 12\space\space 1),6)$ and Principal of Mathematical Induction Alternative Form

1

I'll outline an answer that does not rely on modular arithmetic; it is very similar to Chou's answer but with the details more spelled out. For $n\geq 1$, let $S(n)$ denote the statement $$S(n) : 7\mid(6^{2n+1}+1)\Longleftrightarrow 6^{2n+1}+1=7m, m\in\mathbb{Z}.$$ Base case ($n=1$): $S(1)$ says that $7\mid(6^{2(1)+1}+1)$, and this is true since ...

1

Hint $\$ The inductive step can be intuitively viewed as congruence multiplication \begin{align}{\rm mod}\,\ 7\!:\qquad \color{}{36}\ \equiv&\,\ \ \color{}{1}\\[2pt] 6\cdot 36^{\color{#c00}n}\equiv&\,\ {-}1\ \ \ {\rm i.e.}\ \ P(\color{#c00}n)\\[-4pt] \overset{\rm multiply}\Rightarrow\ \ 6\cdot 36^{\color{#0a0}{n+1}} \equiv&\,\ {-}1\ \ \ ... 1 For n=1 we have 6^{2n+1} + 1 = 6^{3} +1, so 7 \mid (6^{2n+1} + 1). If n \geq 1 is such that6^{2n+1} = 7k - 1$$for some k \geq 1, then$$6^{2n+3} + 1 = 36\cdot 7k - 36 + 1 = 36\cdot 7k - 35=7(36k-5),$$divisible by 7. 1 By assumption, 6^{2(k) + 1} + 1 is divisible by 7, so 6^{2(k) + 1} \equiv -1 \mod7. On the other hand, 6^{2(k+1) + 1} = 6^{(2k+1) + 2}=36*6^{2(k) + 1}\equiv (1)(-1) \mod 7 \equiv -1 \mod 7. Hence 6^{2(k+1) + 1} + 1 is divisible by 7. 0 The number of nodes would be 2^{l-1}, where l is the number of leaf nodes. 0 I've proved it in understandable way, using the very basic approach of induction. The general case P(n) is: 15n^2 \leq 2^n The case P(11) is true: 1815 \leq 2048 And also the case P(12): 2160 \leq 4096 Now, we are supposing that the general case P(n) holds. Starting from 15n^2 \leq 2^n We multiply both sides by 2, getting 30n^2 \leq ... 1 Another approach is to use \frac{15(n+1)^2}{15n^2} = (1+1/n)^2 and \frac{2^{n+1}}{2^n} = 2. 1 Note that 15 n^2 \leq 2^4 n^2, so the given inequality holds if n^2 \leq 2^{n - 4}. But if the latter holds for some fixed n, then$$(n + 1)^2 = \left(1 + \frac{1}{n}\right)^2 n^2 \leq 2 n^2 \leq 2^{n - 3} = 2^{(n + 1) - 4},$$and so it also holds for n + 1. It therefore holds for all n\geq 11 by induction, the case n = 11 being a direct ... 1 Show the base case n=11 and then do the inductive step using your inductive hypothesis to prove the claim. Here's the outline of the inductive step:$$15(n+1)^2=15n^2+30n+15\leq 2^n+30n+15\leq 2^n+2^n=2^{n+1}$$This follows from the trivial fact that 2^n\gt 30n+15~\forall~n\geq 11 since the exponential function grows very quickly compared to the degree ... 1 For a positive decreasing sequence (a_n), we can write the inequality$$\int\limits_{k+1}^{n+1}a(x)dx\leq\sum\limits_{v=k+1}^{n}a_v\leq\int\limits_{k}^na(x)dx$$Then, in special case, taking a_n=\frac{1}{\sqrt{n}}, a(x)=\frac{1}{\sqrt{x}} and k=n-1 you get the desired result. For the other inequality, you can take k=0 in the left side of the ... 5 Hint: Observe that$$\sqrt{n+1}-\sqrt{n}=\dfrac{\left(\sqrt{n+1}-\sqrt{n}\right)\left(\sqrt{n+1}+\sqrt{n}\right)}{\sqrt{n+1}+\sqrt{n}}.$$1 The classical proof start from the lemma: The set \mathbb{N} of positive integers \mathbb{N} = \{0, 1, 2, > \cdots\} is not bounded from above. That can be proved by Peano axioms. Now: na\ge b is equivalent to : n\ge \dfrac{b}{a} and, if such an n does not exists than n<\dfrac{b}{a} for all integers n and this contradicts the ... 1 How about n = b? Then na = ba \geq b. 2 Start with the list of all 2^n vectors of length n of +1s and -1s. Someone changes some of the entries to 0. Show that there is always a non-empty collection of rows which sums to the zero vector. This looks like the perfect case for induction (on n), but the two proofs I'm aware of don't use induction; induction just doesn't seem to help here. 4 1) For all relatively prime positive integers a and m there is a prime number in the arithmetic progression a, a+m, a+2m, a+3m,\dots Of course the general theorem is that there are infinitely many primes in each such progression, but the way I stated it by quantifying over all a and m is equivalent to the general version; for beginners I ... 2 For all n, there is no m such that m < n < m+1. 2 Theorem: For all n\in \mathbb{N},$$ n^2 + 1 \geq 2n. $$Easy to prove by just observing that (x-1)^2 \geq 0 for all x\in \mathbb{R}. Not only is this way quicker than writing out a proof by induction, but it works for all real numbers, not just natural numbers. So you have an easier proof of a stronger result! 3 There's the classic example that$$1 + 2 + \ldots + n = \dfrac{n(n+1)}{2},$$which can be proved without induction using Gauss's trick, or the geometric argument involving a rectangular grid. In a similar vein, showing$${n \choose k} = {n - 1 \choose k - 1} + {n - 1 \choose k} \quad \text{for } 1 \le k \le n - 1$$has a really straightforward ... 3 Answer 1: Assuming the inductive hypothesis, we can say that horses \{2,...,n\} are the same color because that is a set of n-1 horses and the inductive hypothesis states that they must be the same color. The failure in the proof is that when n=2, the two "overlapping sets" do not overlap, so the inductive step from n=1 to n=2 is invalid. Answer ... 3 12=4+4+4 13=4+4+5 14=4+5+5 15=5+5+5 Now, suppose n>15; as the inductive hypothesis you can assume that any number m with 12\le m<n can be written as sum of fours and fives. Then n-4>11 can be written as sum of fours and fives, which implies the thesis also for n. This is indeed a constructive approach: divide n\ge12 by ... 0 In general, the Chicken McNugget theorem says that for any coprime integers p, q, the largest integer that is not of the form px + qy is pq - p - q. So in this case, 11 is the largest integer which cannot be expressed as so, so every integer \geq 12 can. 1 Just to see the pattern: 12=4+4+4. 13=4+4+5. 14=4+5+5. 15=5+5+5. 16=4+4+4+4. Base case: 12. Note that 12=4+4+4. Inductive case. Assume that n can be written as n=4x+5y with x,y \in \mathbb{N}_0. If x>0, then n=4(x-1)+4+5y so n+1=4(x-1)+5(y+1). If x=0, then n=5y so n+1=5y+1. Note y\geq4 (we handled the case ... 6 I think your approach could easily be used for induction and is at least as good as the textbook suggestion of multiple base cases (which is also a perfectly adequate proof). So to build on your ideas, we have: Base case 12=4+4+4 Inductive step Assume true for k\ge 12. Note that we have at least 3 terms in the decomposition of k. We must therefore ... 1 Since an answer how to continue your proof was already given, I want to give another proof not using induction (which is in my eyes not the right way to proof this equality). We have$$\sum_{i=1}^{2n}\frac{(-1)^{i+1}}{i} \overset{(1)}{=} \sum_{i=1}^{n}\frac{1}{2i-1}-\sum_{i=1}^{n}\frac{1}{2i} = ...

1

You got off on the wrong foot with your first step: you want to show that $$\sum_{i=(n+1)+1}^{2(n+1)}\frac1i=\sum_{i=1}^{2(n+1)}\frac{(-1)^{1+i}}i\;,$$ i.e., that $$\sum_{i=n+2}^{2n+2}\frac1i=\sum_{i=1}^{2n+2}\frac{(-1)^{1+i}}i\;.\tag{1}$$ In general I find it a little easier to start with this and figure out how to use the induction hypothesis than it ...

1

$$\sum_{i=n+2}^{2n+2} \frac{1}{i}=\sum_{i=n+1}^{2n}\frac{1}{i}+ \frac{1}{2n+1}+\frac{1}{2n+2}-\frac{1}{n+1}=\sum_{i=1}^{2n}\frac{(-1)^{i+1}}{i}+\frac{1}{2n+1}+\frac{1}{2n+2}-\frac{1}{n+1}$$ It remains to prove that: $$\sum_{i=1}^{2n}\frac{(-1)^{i+1}}{i}+\frac{1}{2n+1}+\frac{1}{2n+2}-\frac{1}{n+1}=\sum_{i=1}^{2n+2}\frac{(-1)^{i+1}}{i}$$ that is $$... 4 As you said, we will induct on n. But the claim will be, for a given n, that \binom{n}{k} is an integer for any k. The base case will be n=1, and indeed \binom{1}{0}=1, \binom{1}{1}=1, and \binom{1}{k}=0 for k\not=0,1. Now assume the claim holds for some n. Then for any k we have$$ \binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}. $$Now ... 2 Assume that k^2>k+1. Then (k+1)^2=k^2+2k+1>k+1+2k+1=3k+2>k+2, because k>0. 0 It seems to me you can use induction and the following transformation on sequences (a_1,\ldots,a_n) of positive integers with a_i\le i and even sum:$$ (a_1,\ldots,a_{n-1},a_n)\mapsto \begin{cases} (a_1,\ldots,a_{n-2})&\text{if}\quad a_{n-1}=a_n,\\ (a_1,\ldots,a_{n-2},|a_n-a_{n-1}|)&\text{if}\quad a_{n-1}\not=a_n. \end{cases} $$The resulting ... 3 Let na_n=b_n. Then, one has$$a_{n+1}=\frac{n}{n+1}a_n\Rightarrow (n+1)a_{n+1}=na_n\Rightarrow b_{n+1}=b_n.$$So, b_n=b_1=a_1. Hence, na_n=a_1, i.e. a_n=\frac{a_1}{n}. 0 Conceivably there is some recurrence that can be proved by induction, but I don’t at the moment see one. However, it’s possible to get an ugly exact formula without using induction. From the Binet formula it’s not hard to deduce that$$F_n=\left\lfloor\frac{\varphi^n}{\sqrt5}+\frac12\right\rfloor$$for n\ge 0. Thus, F_n\le m if and only if ... 6 There is a whole family of examples similar to the proposition that n^3-n is divisible by 6 for each natural number n. Proof by induction isn’t hard, but it’s certainly unnecessarily complicated. 2 For the induction step, you assume that a \in \mathbb{N} and that$$\exists b \in \mathbb{N} . (b \times b \le a) \land (a < (b+1) \times (b+1)). \tag{1}$$Now, depending on exactly how your formal system is formulated, there should be some way to identify a witness for (1), that is, for the inductive step you can introduce a free variable b_0 and ... 3 For all n \in \mathbb{N}, \frac{n}{n+1} < 1. The slick algebraic proof of this would be \frac{n}{n+1} = 1 - \frac{1}{n+1} < 1 since \frac{1}{n+1}>0 for all n \in \mathbb{N}. Induction would be much messier... 0 Cut a square into (n+1) pieces, with one piece across the full width (in green), then n pieces in vertical slices - shown below is the scheme for 7 pieces. Then you can see that the light-blue \frac{1}{n+1} slice added to a \frac 1n portion of the green \frac{1}{n+1} slice - that is, \frac{1}{n+1} + \frac 1n\frac{1}{n+1} - is a \frac 1n ... 0 \frac{1}{n(n+1)}+\frac{1}{n+1}=(\frac{1}{n}-\frac{1}{n+1})+\frac{1}{n+1}. 5$$ \frac{1}{n + 1} + \frac{1}{n(n + 1)} = \frac{n}{n(n + 1)} + \frac{1}{n(n + 1)} = \frac{n + 1}{n(n + 1)} = \frac{1}n $$1 Without explicitly using induction, you can write this one-line proof:$$ n^2-n=n(n-1) \ge 2 \cdot 1 > 1  Induction is implicit in $a \ge a', b \ge b' \implies ab \ge a'b'$.

Top 50 recent answers are included