Induction in general is the inference from the particular to the general. Mathematical induction is not true induction, but is a form of deductive reasoning. Its most common use is induction over well ordered sets, such as natural numbers, or ordinals. While induction can be expanded to class ...

learn more… | top users | synonyms

2
votes
3answers
199 views

A polynomial with integer coefficient

I'm struggling with this question: Suppose $P(x)$ is a polynomial with integer coefficients such that non of the values $P(1),...,P(2010)$ is divisible by $2010$. Prove that $P(n)\neq 0$ for all ...
0
votes
1answer
17 views

Divisibility by induction

I have learnt how to prove expressions by induction based on the use of three assumptions $n=1$, $n=k$, $n=k+1$. But can someone help me prove that $1+10^{2n-1}$ is divisible by $11$
0
votes
0answers
27 views

proving regular expressions by induction [on hold]

i was given this question "Prove formally that L(R∗) = L((R∗)∗). [Hint: you may use proof by induction.]" ((R∗)∗) and (R∗) are basically regular expressions and L would represent it's language i ...
0
votes
1answer
40 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
16 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
86 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 ...
1
vote
0answers
21 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 ...
4
votes
2answers
72 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 ...
0
votes
1answer
16 views

Proof by induction question about fuel depots

You are asked to drive a lunar rover around the moon (which is just a circle in this question). There are (finitely many) fuel depots on the way, with the total amount of fuel stored in them ...
1
vote
1answer
32 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
2answers
29 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 ...
0
votes
2answers
29 views

Proof by induction sum $2^j = 2^{n+1} - 1$

I am trying to solve a previous test for an exam, and there are no solutions. The problem I am trying to solve is If $n$ is a natural number, then $1 + 2 + 2^2 + 2+3 + ... + 2^n = 2^{n+1} -1$ ...
0
votes
0answers
18 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
40 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
34 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: ...
3
votes
1answer
49 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
3answers
39 views

How have they done the algebra here?

Proof by induction Can someone explain these steps to me please? Did the $2^{k-1}$ change to $2^k$ by multiplying numerator by 2?? Even so, if you add them when they have the common denominator, ...
2
votes
3answers
44 views

Proof by induction of a recursive sequence

I am studying CIE A levels Further Maths and I am stuck at a question from June 2002: Q The sequence of positive numbers $u_1,u_2,u_3,...$ is such that $u_1<4$ and ...
0
votes
3answers
57 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
33 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
1answer
35 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
45 views

Strong induction inequality proof

Use strong induction to prove that $$\frac{1}{2^3}+\frac{1}{3^3}+\cdots+\frac{1}{n^3}\leq\frac{5}{8}-\frac{1}{n}$$ $$n\geq2$$ I'm not sure how to go about this. I used base cases n=2, and n=3 but ...
1
vote
1answer
64 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
23 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
6answers
58 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
21 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
30 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
5answers
71 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
1answer
28 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
43 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$}$$
1
vote
1answer
26 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 ...
3
votes
1answer
36 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 ...
0
votes
1answer
59 views

Proof by Induction Algorithm [closed]

I am stuck on trying to prove this algorithm using mathematical induction. ...
0
votes
3answers
43 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 ...
3
votes
3answers
86 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
2answers
13 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 ...
-1
votes
1answer
73 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
1answer
62 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
0answers
16 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) ...
1
vote
0answers
44 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
2answers
50 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
22 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
24 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 , ...
2
votes
2answers
42 views

Proof by induction for divisibility by power of 2^n

I'm trying to prove, using strong induction, that $2^n$ divides $a_{n}$ where: $$a_{n} = 2a_{n-1} + 4a_{n-2}$$ Given that $a_{1} = 2$ andn $a_{2} = 8$ What I've got so far: Base Case $$n = 1$$ ...
3
votes
3answers
43 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$: $$ ...
2
votes
7answers
63 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 ...
0
votes
4answers
36 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
39 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
18 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. $$ ...
0
votes
1answer
21 views

Prove summation by Induction

Prove this by induction n ∑ i(i!) = (n+1)!-1 i=1 So I wrote: ...