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 aimed ...

learn more… | top users | synonyms

0
votes
1answer
51 views

Everyone has brown eyes [duplicate]

I'm going to prove that everyone's eyes are the same color. Ready? If there is only one person, then it's obviously true; this person's eyes are the same color that this person's eyes. Suppose it is ...
1
vote
1answer
155 views

Round robin algorithm proof

I need to prove by induction the theorem that says we can construct a round robin tournament: Given a tournament with $2^k$ teams. We label the teams $t_1, t_2, ..., t_{2^k}$. It is possible to ...
2
votes
5answers
120 views

Hint in Proving that $n^2\le n!$

The problem is to find the values of n such $n^2\le n!$. I have found this set to be {${n\in Z^+| n\le1 \lor n\ge 4}$} I've used a proof by cases to prove the first part ($\forall n\le 1$) which was ...
0
votes
3answers
79 views

What are the coefficients of the polynomial inductively defined as $f_1=(x-2)^2\,\,\,;\,\,\,f_{n+1}=(f_n-2)^2$?

Let $\{f_n(x)\}_{n\in \Bbb N}$ be a sequence of polynomials defined inductively as $$\begin{matrix} f_1(x) & = & (x-2)^2 & \\ f_{n+1}(x)& = & (f_n(x)-2)^2, &\text{ for all ...
1
vote
0answers
44 views

Use of mathematical induction to compute $\int_0^{\pi/2} \sin^{2n+1}xdx$?

We are given a reduction formula for $\int \sin^n xdx$, namely $$\int \sin^nxdx = -\frac{1}{n}\sin^{n-1}x\cos x + \frac{n-1}{n}\int \sin^{n-2}xdx.$$ I know how to derive this reduction formula. How ...
5
votes
2answers
89 views

$a_1a_2\cdots a_n = 1 \implies a_1 + a_2 + \cdots + a_n \geq n$ if $a_1, a_2, \dots, a_n > 0$

Let $a_1, a_2, \dots, a_n > 0$. I'm trying to prove that if $a_1a_2\cdots a_n = 1$, then $a_1 + a_2 + \cdots + a_n \geq n$ by mathematical induction without using the AM-GM inequality. So far I've ...
2
votes
1answer
45 views

sum of an arctan series using mathematical induction

How to solve this problem using mathematical induction: $$\arctan (1) + \arctan \Big(\frac13\Big) + ... + \arctan \bigg(\frac{1}{n^2+n+1}\bigg)=\arctan (n+1)$$
1
vote
1answer
338 views

Assuming inequalities to be equal when proving by induction

I was struggling to get my head around proof by induction for inequalities when I came across a method described at The Math Forum (first answer). Here Dr. Ian goes ahead and compares the changes in ...
1
vote
2answers
40 views

induction on matrices with powers + addition and limit

$A= \begin{bmatrix} 1-q && p \\ q && 1-q \end{bmatrix}, 0<p<1, 0<q<1,$ Using mathematical induction show that $A^n$ = $\frac{1}{p+q}\begin{bmatrix} q && p \\ q ...
1
vote
0answers
162 views

Variation of Nim: Player who takes last match loses

Here is a homework problem I can't understand the solution to. Can anyone help me understand why they are using "mod 4"? Can someone help me understand this strong induction example? Thanks everyone! ...
0
votes
2answers
102 views

Prove by induction that $(1+x)^n \geq 1+nx$ [duplicate]

Prove by induction that $\forall x \in \mathbb{R}, x \geq -1, \forall n \in \mathbb{N},n \geq 0$ that $$(1+x)^n \geq 1+nx$$ First of all I have a problem with x being a real number, how can I use ...
3
votes
0answers
82 views

Cauchy-Euler Equation of order $n$

What I wish to prove is that for a Cauchy-Euler equation of order $n$, the substitution $x=e^{t}$ transforms it into a linear differential equation with constant coefficients. To put it as a theorem: ...
0
votes
1answer
65 views

Induction proof with no terms of sequence

The sequence $[x_n]$ is given by $x_1=1$ and $x_{n+1}=\displaystyle\frac{4+x_n}{1+x_n}$ for $n\ge 1$. Prove by induction that for $n\ge 1$, ...
3
votes
1answer
60 views

Proving that $(a+b+c)^n=a^n + b^n + c^n$

Suppose that $(a+b+c)^3=a^3 + b^3 + c^3$. For what positive integer values of n is it true that $(a+b+c)^n=a^n + b^n + c^n$. Any hint will be much appreciated
1
vote
1answer
32 views

How does mutual induction work?

In my understanding you use the Induction Hypothesis to back up your argument, but what doesn't make sense to me is that we use the Induction Hypothesis even though the Induction Hypothesis wasn't ...
0
votes
2answers
61 views

Induction, show that something is smaller then …

I have to show the following by induction. $1 \cdot 2 \cdot 3 ... (n - 1) \leq (\frac{n}{2})^{n -1}$ As it is homework I "only" need a push in the right direction. my thought is that is something ...
2
votes
2answers
42 views

Mathematical Induction for divisibility by $7$

Not entirely sure if this is where I should post, but I need help. I need to prove $7\mid (9^n - 2^n)$ for all $n\ge 1$. I have the parts for $n = 1$. But when it comes to solving $k \implies k+1$, ...
0
votes
2answers
157 views

Use Bonnet recursion formula to prove by induction

Use Bonnet recursion formula: $P_{n+1}(x) = \frac{2n+1}{n+1} x P_n(x) - \frac{n}{n+1} P_{n-1}(x)$ to prove by induction 1) $P_n(1) = 1$ for all $n$ 2) $P_n(-x) = (-1)^n P_n(x)$ for all $n$ an for ...
0
votes
1answer
38 views

Could someone explain me this induction.

I'm trying to understand a paper called "Diameter of Polyhedra: Limits of Abstraction" available here : http://sma.epfl.ch/~eisenbra/Publications/designs.pdf My problem is with the first two ...
1
vote
1answer
66 views

so Thinking about induction proofs

So I'm studying some induction proofs, but I have some questions that were not clear to me when I read the book's definition. I want to know if my understanding is correct: So, for me, and ...
0
votes
1answer
28 views

Induction when not dealing with Sigma notation

How do you prove $4^n > 3^n + 2^n$ using induction? Base case would be when $n = 2$, $16 > 13$. Then assume $n = k$ so that $4^k > 3^k + 2^k$. Then let $n = k + 1$ so that $4^{k+1} > ...
0
votes
5answers
88 views

Prove that $\sum\limits_{k=0}^n\ 2\times3^{k-1} = 3^n-1$

Hope someone can enlighten me on how to show via induction that $\sum\limits_{k=0}^n\ 2\times3^{k-1} = 3^n-1$
0
votes
6answers
94 views

Why is this contrapostive assumed to be true?

I have a problem with the following logical deduction: $ incabal(Darren) \implies incabal(Martyna) $ This would read, "If Darren is in the cabal, then so is Martyna." Later in the homework we ...
1
vote
2answers
36 views

How to prove $\sum\limits_{k=0}^n\ (3k^2+2k+1) = n^3 + 5 \begin{pmatrix}n+1\\2\end{pmatrix}+1$

$\sum\limits_{k=0}^n\ (3k^2+2k+1) = n^3 + 5 \begin{pmatrix}n+1\\2\end{pmatrix}+1$ How would you go on proving this equation? Doesn't have to be induction..
0
votes
1answer
46 views

Proof by induction valid or not?

Prove by induction the following: $$\sum_{i=0}^n x^i = \frac{1-x^{n+1}}{1-x}$$ We want: $$x^0+x^1+ \ldots + x^n = \frac{1-x^{n+1}}{1-x}$$ I try this for $i=1$ and it works, so I have an initial ...
0
votes
1answer
41 views

How to use induction on this type of inequality?

Given $a_1,a_2,\ldots,a_n>0$ and $a_1+a_2+\ldots+a_n<\frac{1}{2}$, prove that $(1+a_1)(1+a_2)\ldots(1+a_n)<2$. Some of you may have already seen this inequality. I was the one who asked ...
0
votes
1answer
71 views

Solving the LaPlace PDE by complete induction

I have a problem with an induction step that appears to be bothersome for me to comprehend it. Problem: Show that $f(x_1, \dots ,x_n)=(x_1^2+ \dots + x_n^2)^{1- n/2}$ for $(x_1^2 + \dots + ...
0
votes
1answer
52 views

Induction proof that $4^n > 3^n+2^n$ for $n\ge2$

This is a problem with induction and proofs but I'm not sure how to start with proving this one. $$\text{Show that for any $n \geq 2$, $4^n > 3^n+2^n$}$$
3
votes
1answer
38 views

Where did this “+1” term come from for this inductive proof?

Where did this "+1" term come from for this inductive proof? It is in boxed in black. For context, We are trying to prove this sequence: has the following solution: $$x_{ n }=\frac { 3^{ n+1 ...
3
votes
2answers
206 views

Proof of definite integral $\int_0^{\pi/2} \frac{\sin(2n+1)x}{\sin x}dx=\frac\pi2$ using induction

Prove by induction or otherwise that $$\int_0^{\pi/2} \frac{\sin(2n+1)x}{\sin x}dx=\frac\pi2$$ for every integer $n\ge0$. How to prove the above question? Can it be proved without using induction?
0
votes
1answer
72 views

Proof by Induction Algorithm [closed]

I am stuck on trying to prove this algorithm using mathematical induction. ...
0
votes
3answers
61 views

Finding the Formula For the Sum of a Sequence

In the problem below, It is asked to find the formula for the sum of the sequence and then to prove whether it is true or false for all n values using induction. $$ 1 + 4 + 7 + ... + (3n + 1), \ n\in ...
0
votes
2answers
19 views

Recursion, Explicit Equasion

Prove $\ a_{n}<2^{n} $ for every natural number n, where $\ a_{n} $ is defined recursively by $$ a_{1}=1, a_{2}=2, a_{3}=3, a_{n}=a_{n-3}+a_{n-2}+a_{n-1},\ for\ n>=4$$ Once I get the explicit ...
-2
votes
1answer
85 views

How do you prove n(n-1) by induction? [closed]

I am able to see how you can prove $n(n+1)$ by induction, but $n(n-1)$ doesn't seem to work. $n(n-1)$ is basically the formula to find the total number of edges possible in an directed graph. ...
0
votes
0answers
23 views

Probability of a Union of Events

Using induction, prove the following statement: Let $A_n$ represent different events. Let $P(A_n)$ represent the probability of the event occurring. $P[A_1 \cup A_2 \cup ... \cup A_n] \leq P(A_1) ...
0
votes
3answers
429 views

Prove that $\log(x) < x$ for $x > 0$, $x\in \mathbb{N}$.

I'm trying to prove $ \log(x) < x$ for $x > 0$ by induction. Base case: $x = 1$ $\log (1) < 1$ ---> $0 < 1$ which is certainly true. Inductive hypothesis: Assume $x = k$ ---> $\log(k) ...
1
vote
0answers
57 views

Inductive proof about Jensen's inequality

The base case is easy. For the inductive step, i take $\lambda$ and $x$ to be as given, and then when I consider $f(\lambda_1 x_1 + . . . + \lambda_n x_n + \lambda_{n+1} x_{n+1})$ I get this is ...
0
votes
1answer
49 views

Show that this summation is an invariant of the loop in algorithm

I'm having trouble with induction with this specific problem. a) Show that $\sum_{i=0}^k 2^i = 2^{k+1} - 1$ is an invariant of the loop in algorithm ...
0
votes
1answer
29 views

For $f: \mathbb{R}^n \to \mathbb{R}$ homogenous, show that $\sum_{i=1}^n x_i \frac{\partial f}{\partial x_i}(x_1, \dots ,x_n)= kf(x_1, \dots , x_n)$

Definition: A function $f: \mathbb{R}^n \to \mathbb{R}$ is said to be homogenous of degree $k$ if $\forall t \in \mathbb{R}$ and $(x_1, \dots , x_n) \in \mathbb{R}^n$ the equations $f(tx_1, \dots , ...
3
votes
3answers
164 views

Prove that, for any positive integer n: $(a + b)^{n} \leq 2^{n-1}(a^{n}+b^{n})$

Prove that, for any positive integer n: $(a + b)^{n} \leq 2^{n-1}(a^{n}+b^{n}) $ I tried induction theorem, when $n = 1$ it is obviously right. But, say $n=k$, It does not make sense since I cannot ...
2
votes
7answers
65 views

$7\mid 2\cdot8^n+3\cdot15^n+2$ is divisible by 7?

I tryed a lot of ways to prove that and I can't. My formula is: $$ 2\cdot8^n+3\cdot15^n+2 $$ And I need to prove if is divisible by 7. Recently I got: $$ 2\cdot8^1+3\cdot15^1+2 $$ $$ 63 $$ And ...
3
votes
3answers
48 views

$19 \mid 2^{2^{n}} + 3^{2^{n}} + 5^{2^{n}}$

I tried to demonstrate the next equation is divisible by 19: $$ 2^{2^{n}} + 3^{2^{n}} + 5^{2^{n}} $$ When $n$ is $1$: $$ 2^{2^1} + 3^{2^1} + 5^{2^1} $$ $$ 4 + 9 + 25 = 38 $$ When $n$ is $k$: $$ ...
0
votes
4answers
41 views

Show that a number divides

How do I show that for all integers $n$, $n^3+(n+1)^3+(n+2)^3$ is a multiple of $9$? Do I use induction for showing this? If not what do I use and how? And is this question asking me to prove it or ...
1
vote
1answer
66 views

Proof by induction of propositional formulas

I have two inductively defined operations: $\text{bin}$ base case: If $p$ is a propositional letter, then $\text{bin}(p) = 0$ inductive step $\text{bin}(\neg \phi) = \text{bin} (\phi)$ ...
0
votes
1answer
28 views

Proving sequence statement using mathematical induction, $d_n = \frac{2}{n!}$

I'm stuck on this homework problem. I must prove the statement using mathematical induction Given: A sequence $d_1, d_2, d_3, ...$ is defined by letting $d_1 = 2$ and for all integers k $\ge$ 2. $$ ...
3
votes
1answer
152 views

Mathematical induction--When it can and can't be used

I'm working through a problem set on mathematical induction. One of the problems asks you to prove that for all $n\in\mathbb N$, $$\sum_{i=0}^{n}8n-5=4n^2-n.$$ I don't have a problem proving this, ...
0
votes
3answers
67 views

If $a$ and $b$ are relatively prime then so are $a$ and $b^n$ for every positive integer $n$

I have been asked to prove the following via induction (as the textbook as suggested): If $a$ and $b$ are relatively prime then so are $a$ and $b^n$ for every positive integer $n$ So, I did the ...
0
votes
1answer
22 views

Prove summation by Induction

Prove this by induction n ∑ i(i!) = (n+1)!-1 i=1 So I wrote: ...
2
votes
2answers
67 views

Some rather non-traditional forms of mathematical induction.

The definition of induction that most of us are familiar with is this: If statement $S$ is true for $1$, and $$S \text{ is true for } n\implies S \text{ is true for }n^+$$ then $S$ is true for all ...
-1
votes
1answer
104 views

Use Mathematical Induction to prove that $\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} +…+\frac{1}{n(n+1)}=1-\frac{1}{n+1}$

Use Mathematical induction to prove that for all integers, $n$ is greater than or equal to $1$. I am confused on what to do after I do the the basis step that is using $n$ as $1$. $$\frac{1}{1 \cdot ...