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

5
votes
2answers
90 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 ...
1
vote
1answer
44 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 ...
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)$$
0
votes
1answer
50 views

A problem on mathematical induction [closed]

This question I am feeling very difficult to solve. It is said to be a problem on mathematical induction: On a circular path, there are are $n$ cars and among them they have enough fuel to cover ...
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 ...
0
votes
2answers
116 views

Proof by induction that $\sum_{j=0}^n 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$ ...
1
vote
0answers
163 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
103 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: ...
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
3answers
53 views

How have they done the algebra here?

Proof by induction \begin{align}&4-\frac{k+2}{2^{k-1}}+(k+1)\left(\frac12\right)^k\\ =&4-\frac{2(k+2)}{2^k}+\frac{k+1}{2^k} \\ =&4-\frac{(k+1)+2}{2^{(k+1)-1}} \end{align} Original image ...
2
votes
3answers
131 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
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$, ...
2
votes
1answer
87 views

Induction: Sum of the squares of 6 consecutive natural numbers

Define for every natural n: $$ a_{n}=\sum\limits_{i=0}^{5}(n+i)^2$$ in other words, $\ a_n$ is the sum of the squares of 6 consecutive natural numbers, the first number is $n^2$ and the last is ...
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
96 views

Strong induction inequality $\frac{1}{2^3}+\frac{1}{3^3}+\cdots+\frac{1}{n^3}\leq\frac{5}{8}-\frac{1}{n}$

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
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
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
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$
1
vote
6answers
287 views

Prove that $\sum_{k=0}^n k^2{n \choose k} = {(n+n^2)2^{n-2}}$

Prove that: $$\sum_{k=0}^n k^2{n \choose k} = {(n+n^2)2^{n-2}}$$ i know that: $$\sum_{k=0}^n {n \choose k} = {2^n}$$ how to get the (n + n^2)?
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
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$}$$
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 ...
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 ...
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 ...
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
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
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
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) ...
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
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
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 , ...
2
votes
2answers
74 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
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$: $$ ...
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 ...
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. $$ ...
0
votes
1answer
22 views

Prove summation by Induction

Prove this by induction n ∑ i(i!) = (n+1)!-1 i=1 So I wrote: ...
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, ...
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 ...
8
votes
2answers
50 views

How to prove an inequality

$a$, $b$, $c$, $d$ are rational numbers and all $> 0$. $\max \left\{\dfrac{a}{b} , \dfrac{c}{d}\right\} \geq \dfrac{a+c}{b+d}\geq \min \left\{\dfrac{a}{b} , \dfrac{c}{d}\right\}$ Hope someone ...
1
vote
1answer
30 views

Discrete Math Induction: $\sum^n_{i=1} \frac1{i(i+1)}$ [duplicate]

For $\sum^n_{i=1} \frac1{i(i+1)}$ Find a formula and proofs that it holds for all n ≥ 1. How would I find the formula for this one that can hold for all n ≥ 1?