For questions about mathematical induction, a method of mathematical proof. Mathematical induction generally proceeds by proving a statement for some integer, called the *base case*, and then proving that if it holds for one integer then it holds for the next integer. This tag is primarily meant ...

learn more… | top users | synonyms

7
votes
2answers
289 views

Number or regions formed when $n$ points on a circle are joined

The maximum number $R_{n}$ of regions formed when $n$ points on a circle are joined in pairs is $\frac{1}{24}\left(n^{4}-6n^{3}+23n^{2}-18n+24\right)$. This is a fact that I have read in several ...
1
vote
4answers
74 views

How to prove an identity containing binomial coefficients

I am trying to prove the identity $$\sum_{k=1}^n (3^k - 1) \binom{n}{k} = 4^n - 2^n$$ where $\binom{n}{k}$ is the binomial coefficient n over k or n choose k.
2
votes
2answers
66 views

Proving $n! \ge 2^{n-1 }$for all $n\ge1 $by mathematical Induction

Im trying to solve the following question In the second step where do they get $k!=2^k-1?$
4
votes
4answers
178 views

Proving $(x+y)^n = \sum\limits_{k=0}^n \binom{n}{k} x^k y^{n-k}$ [duplicate]

I'm reading Serge Lang's 'Analysis I', and there's a problem I cannot figure out how to prove: Problem: Prove by induction that $$(x+y)^n = \sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix} x^k ...
0
votes
2answers
133 views

Revisited: Binomial Theorem: An Inductive Proof

I'm asked to use the fact that $\begin{pmatrix}n\\r\end{pmatrix}+\begin{pmatrix}n\\r-1\end{pmatrix}=\begin{pmatrix}n+1\\r\end{pmatrix}$ to show, by induction, that ...
0
votes
2answers
30 views

Formalized attempt of proof that well ordered-ness ( of subsets of $\mathbb{Z}$ that are bounded below) implies induction seems to have issue?

I want to prove that well-orderedness on the integers implies induction. The proof is the classical "assume a contradiction" and see what happens. So begin with an intended contradiction: ...
5
votes
2answers
904 views

Flaw in this proof by induction

I'm trying to find a flaw in the following proof, but I am unsure if I am correct or not: Identify the flaw in the proof that $2n = 0$ for all $n \ge 0$. Base case: If $n=0$ then $2\cdot n = 2\cdot ...
4
votes
3answers
65 views

Proof of $n^{1/n} - 1 \le \sqrt{\frac 2n}$ by induction using binomial formula [duplicate]

Using $$(a+b)^{n} = \sum_{i=0}^n {n \choose k} a^{n-k} b^{K}$$ prove that $$n^{1/n} - 1 \le \sqrt{\frac 2n}$$ for n= 2,3,4.... I know the first step is to set $$ n^{\frac 1n} = 1 + x $$ for some ...
15
votes
3answers
2k views

9 pirates have to divide 1000 coins…

A band of 9 pirates have just finished their latest conquest - looting, killing and sinking a ship. The loot amounts to 1000 gold coins. Arriving on a deserted island, they now have to split up the ...
5
votes
1answer
8k views

Prove by mathematical induction that $n^3 - n$ is divisible by $3$ for all natural number $n$

I'm working on a task where I'm a bit unsure if the answer I've got is correct. Here is the task: Show by induction that the following assertion is true for all natural numbers $n$ $n^3 - ...
0
votes
1answer
39 views

Proof by induction that *p* = 1/*p*-1 in golden rectangle exercise

The initial rectangle's dimensions is L0 for the length and l0 for the width. A golden rectangle can be obtained when it has the same proportions as the initial rectangle, so p = L0/l0 I am first ...
1
vote
2answers
37 views

induction of sequence

I am really stuck on one of my excersies. I know it's true for n=1, but I can figure out how to prove it for k+1. This excersise it considerably more difficult than the one we discusses in class. I ...
0
votes
0answers
9 views

Proof By induction on inequality [duplicate]

I'm trying to answer this question: Let $x > −1$. Prove by induction that $(1 + x)^n \ge ≥ 1 + nx$ for all $n ∈ ℕ$ All I have been able to prove up until now is that the base cases hold. ...
1
vote
1answer
31 views

proof by induction in worded example

I'm trying to answer the following question: The boxes Banana Ltd. uses to ship bananas come in two sizes, one that holds three bananas and one that holds five bananas. The company promises to ...
2
votes
4answers
70 views

How can the proof by induction be reliable when it depends on the number of steps?

Yesterday, I got a math problem as follows. Determine with proof whether $\tan 1^\circ$ is an irrational or a rational number? My solution (method A) I solved it with the following ways. I ...
-1
votes
1answer
63 views

Find the smallest $N \in Z^+$ satisfying the property that $n^2 \leq 2^n$ for all $n \geq N$, and prove your result using induction.

Find the smallest $N \in Z^+$ satisfying the property that $n^2 \leq 2^n$ for all $n \geq N$, and prove your result using induction. I assume this can be done simply by testing it will random N ...
0
votes
2answers
102 views

Prove that a set having $n\geq 2$ elements has $\frac{n(n-1)}{2}$ subsets having exactly two elements.

I want to prove this by induction. I have everything up to proving $k+1$. I know I want to show that a set having $k+1$ elements has $\frac{k(k+1)}{2}$ but I'm struggling to find the beginning step ...
3
votes
5answers
490 views

Why induction can't work for infinite number? [closed]

Loosely speaking, there is no such number n+1= infinity. Is there any way to prove that induction can not work for infinite numbers in formal way?
0
votes
2answers
80 views

Proving a log by induction

I had a test recently and there was a log question that was $$3\log_3(x) - 4\log_3(x) + 1/2\log_3(x).$$ When I solved it I got $$\log_3 \left(\frac{1}{\sqrt{x}}\right).$$ My teacher says that is ...
1
vote
1answer
67 views

What's wrong with this (fake) proof that $ n=1\forall n\in \Bbb N$?

What's wrong with this (fake) proof that $ n=1\forall n\in \Bbb N$? Base case: $n=1$ true. $n-2,n-1<n+1\implies n-1=n-2\implies n+1=n=1$. From the principle of induction it follows that $n=1 ...
2
votes
2answers
436 views

Induction proof: n lines in a plane

Assume that there are $n$ infinitely long straight lines lying on a plane in such a way that no two lines are parallel, and no three lines intersect at a single point. Prove that these lines divide ...
0
votes
1answer
33 views

prove the inequality by induction for the folfowing expression

1+1/2+1/3+1/4+.....+1/2^n>=1+n/2 I gOt stuck after 3rd step because I can't represent 3rd expression with the help of second one as there are other numbers between 1/2^k and 1/2^(K+1)
0
votes
2answers
56 views

proof by induction, the number of ways of grouping unlabelled objects

How can i prove by induction that, while grouping n unlabelled objects into m groups, $$ f(n,m) = { n+m-1 \choose m-1 }$$ This is the step i could get to, after assuming true for k, for some k+1, I ...
0
votes
1answer
93 views

Prove by induction that if the first car stops, then all cars will stop

$n$ cars are travelling down a narrow one-way street. We know that: The distance $d$ between each two cars is the same. The safe breaking distance $b$ is the minimum distance between ...
0
votes
2answers
124 views

Graph Proof by induction.

Can you prove via induction that there exists a node in a directed graph of n nodes that can be reached in at most two edges from every other node in the graph. Every node in the graph is required to ...
0
votes
0answers
45 views

Is this a proper way to inductively prove the theta bound of a recurrence relation?

Sorry for the messy work, but it's late. The problem at hand is to find and prove a theta-bound for the following recurrence relation: $T(n) = n{\frac{1}{2}}T(n^{\frac{1}{2}})+nlog(n)$ Claim: ...
1
vote
1answer
60 views

Proof by induction on an inequality

Prove $3^{n+1} > n^4$ such that $n \in \mathbb{N}$, $n \neq 3, n \neq 4$. Let P(n) be the statement "$3^{n+1} > n^4$ such that $n \in \mathbb{N}$, $n \neq 3, n \neq 4$." I have proved the base ...
3
votes
0answers
51 views

Prove $\binom{n}{k} = 0$ for $n = 0, 1, … , k-1$

It's a homework problem. Prove $\binom{n}{k} = 0$ for $n = 0, 1, ... , k-1$ I think induction needs to be used, I can do $n = 0$ (and $n = 1$ since our teacher likes us to do the first two), but $n ...
4
votes
2answers
54 views

What is the best way to show the monotonicity of this recursive sequence?

This is the sequence: $a_{n+1}$ = $\sqrt{3a_{n} - 2}$ $a_{0}$ = 3 Before evaluating monotonicity I know that the sequence is converting towards either 1 or 2. My approach is to assume it is ...
1
vote
2answers
32 views

Prove: $n \in Z^{\geq 2}$, $f_nf_{n+1} - f_{n-1}f_{n+2} = (-1)^{n+1}$

$n \in Z^{\geq 2}$, $f_nf_{n+1} - f_{n-1}f_{n+2} = (-1)^{n+1}$. How do you do the inductive step of this proof, every time I do it I cannot find a way to use the definition of a Fibonacci sequence to ...
1
vote
3answers
70 views

Prove that $1^2 - 2^2 + 3^2 - 4^2 + \cdots + (-1)^{n-1}n^2 = \frac12(-1)^{n-1} n (n + 1)$, where $n $ is a positive integer

Prove that $1^2 - 2^2 + 3^2 - 4^2 + \cdots + (-1)^{n-1}n^2 = \frac12(-1)^{n-1} n (n + 1)$, where $n $ is a positive integer How do I prove the above expression using mathematical induction? So ...
-2
votes
1answer
40 views

Prove that for all $n \in \mathbb{Z}^+$, $\sum_{i=1}^n i^3 = \left(\sum_{i=1}^n i\right)^2$. [duplicate]

Prove that for all $n \in \mathbb{Z}^+$, $\sum_{i=1}^n i^3 = \left(\sum_{i=1}^n i\right)^2$. I understand how to do the base case using the proof of induction, but I don't know how you would show the ...
2
votes
2answers
46 views

There is a best performer in a round robin tournament

At a social bridge party every couple plays every other couple exactly once. Assume there are no ties. If $n$ couples participate, prove that there's best couple in the following sense: A couple ...
1
vote
2answers
45 views

Prove that $f_n = \frac{\alpha^n - \beta^n}{\alpha - \beta}$ for all $n \in \mathbb Z^+$.

Let $\alpha = \frac{1+\sqrt{5}}{2} \hskip 20pt \beta = \frac{1-\sqrt{5}}{2}$ be the two real roots of the quadratic equation $x^2 - x - 1 = 0.$ Prove that $f_n = \frac{\alpha^n - \beta^n}{\alpha - ...
3
votes
1answer
45 views

Proving the gcd of two integers expressed as recursive statements

I have the following problem: Let $a$, $b$ be positive integers and $(x_{n})_{n\geq 0}$ be a sequence of integers defined by the following formulas: $x_{0}=0$, $x_{1}=a$, $x_{n}=x_{n-2}+bx_{n-1}$ ...
0
votes
1answer
55 views

Induction problem prove that at least one of the coefficients Cn is even

For $n \in \mathbb{N}$ regard $1+x+x^2$ as a polynomial, i.e., $$(1+x+x^2)^n = \sum C_n(x^n)$$ with $C_n \in \mathbb{N}$, and prove that at least one of the coefficients $C_n$ is even. I really ...
3
votes
4answers
109 views

How do you prove $37^{100} - 37^{20}$ is a multiple of $10$ using induction?

I've tried making it $37^{5n} - 37^n$ is a multiple of $10.$ Then I made the base case be $n = 0,$ so $1 - 1 = 0$ which is a multiple of $10.$ I assumed $37^{5n} - 37^n$ is a multiple of $10$ for all ...
1
vote
0answers
51 views

How to prove by induction that $(n+1)^n < n^{n+1}$ for $n\ge 3$? [duplicate]

Here is an inequality (let's call it - "$A(n)$") that has to be proved: $$ (n+1)^n < n^{n+1} \text{ for } n\ge3. $$ I'll skip the first two steps of induction and move right to the induction step ...
1
vote
3answers
90 views

Induction: $\sum_{k=1}^{2n} (-1)^k k = n$

Use the proof of induction to show : $\sum_{k=1}^{2n} (-1)^k k = n$ I know how to show the base step of this problem, but in showing the inductive step I am having trouble determining how to show ...
1
vote
0answers
60 views

Show inequality of recursive defined exponantial function.

Given the following function: $f(1) = 2$ $f(x+1) = 2^{f(x)}$ Show that $f(i) > f(i-1)^{i-1}$. Starting with some $i > i_0$. Intuitively I can easily see why this is so. Basically ...
0
votes
2answers
45 views

Math induction problem. [duplicate]

How to prove the following with induction? $$\sum_{k=1}^{2n} \frac{1}{k(k+1)} = \frac{2n}{2n+1}$$ I have difficulty solving this example. I got past base part where I prove that $L(1) = P(1)$ but I ...
1
vote
1answer
51 views

Why does the conclusion of induction proofs hold even when the base case is greater than $1$?

The principle of mathematical induction states that if $X\subseteq \mathbb{N}$ satisfying $1\in X$ and if $k\in X$ for all $k<n$, then $n\in X$. Then $X=\mathbb{N}$. Now, consider the claim: ...
1
vote
2answers
45 views

Determining a rule for the remainder when $3^n$ is divided by $13$

After some direct calculations, it appears that the powers of $3$ form a cycle of $1$, $3$, and $9$ when divided by consecutive powers of $n$. For example $$3^0 \equiv 1 \pmod{13}, 3^1 \equiv 3 ...
1
vote
1answer
29 views

How to generalize induction from this definition?

Definition: An inductive set $A$ is a one that satisfies: $1\in A$ and $k \in A\implies k+1\in A$. If we characterize the natural numbers as the set which has the following properties: $\Bbb N$ is ...
1
vote
4answers
49 views

Proof by Induction for Natural Numbers

Show that if the statement $$1 + 2 + 2^{2} + ... + 2^{n - 1} = 2^{n}$$ is assumed to be true for some $n,$ then it can be proved to be true for $n + 1.$ Is the statement true for all $n$? ...
1
vote
2answers
55 views

Use Proof of Induction to prove $\sum_{k=1}^{2n} (-1)^k k = n$

Base Case: \begin{eqnarray*} \sum_{k=1}^{2n} (-1)^k k = n\\ (-1)^1 (1) + (-1)^2(2) &=&1 \\ 1=1 \end{eqnarray*} Inductive Step: For this step we must prove that \begin{eqnarray*} ...
2
votes
2answers
67 views

Is my induction proof of $2^{n} > 2n+1$ correct?

Hello I am wondering if anyone can conform that the method I use in the following proof is valid. If not please inform me/ point me in the right direction. It is a very basic question, i.e. to prove ...
4
votes
1answer
70 views

inequality of two functions

I have the following problem. I need to show that $b(i)>b(i-1)^{i-1}$ for $i>k$ for some $k$. $b$ is the following function: $b(1)=2$ and $b(n)=2^{b(n-1)}$ I tried to do this by induction, but ...
0
votes
4answers
31 views

How did the solution to this system of equations get a power of n?

I have been reading up on how to solve problems relating to ideal gases. In a certain example problem in the book, Questions and Problems in school Physics by Tarasov and Tarasova, a system of ...
0
votes
1answer
38 views

Proof By Induction for arbitrary integers [closed]

Assume that $|x + y| \leq |x| + |y|$ for all $x,y \in {Z}.$ Use this assumption and induction to prove that $$|a_1 + a_2 + ... + a_n| \leq |a_1| + |a_2| + ... + |a_n|$$ for all integers $n \geq 2$ ...