Tag Info

New answers tagged

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 that $$6^{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 $+1$s and $-1$s. 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

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