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

0
votes
2answers
93 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
81 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
59 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
119 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
85 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
87 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
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
35 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
44 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
285 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
40 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
31 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
70 views

Proof by Induction Algorithm [closed]

I am stuck on trying to prove this algorithm using mathematical induction. ...
0
votes
3answers
59 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
203 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
18 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
70 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
53 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
138 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
47 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
28 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
72 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
46 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
40 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
65 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
27 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: ...
3
votes
1answer
138 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
64 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
49 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?
-1
votes
2answers
65 views

Discrete Math On Induction proof: $\sum_{i=1}^n n2^n = (n-1)2^{n+1} + 2$ [duplicate]

Show by induction that the following formulas hold. $\sum_{i=1}^n n2ⁿ = (n-1)2^{n+1} + 2$ What did a similar problem to this but this one is a little different. I think is because this one has a ...
0
votes
3answers
65 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 ...
-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 ...
0
votes
3answers
301 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) ...
0
votes
1answer
38 views

Prove uniqueness of recursive function

I am currently reading Cutland's Computability and would like to figure out how to solve Theorem 4.2 which states: Let $x=(x_1 \dotsc x_n)$, and suppose that $f(x)$ and $g(x,y,z)$ are functions; ...
0
votes
1answer
27 views

$lcm(a_{1},…,a_{n})=lcm(lcm(a_{1},…,a_{n-1}),a_{n})$

I tried to prove this by complete induction on $n$ but I am having problems in the inductive step: Suppose $$lcm(a_{1},...,a_{n})=lcm(lcm(a_{1},...,a_{n-1}),a_{n}) \forall k\le n\in \mathbb ...
6
votes
0answers
171 views

My first proof that uses the well-ordering principle (very simple number theory). Please mark/grade.

What do you think about my first proof that uses the well-ordering principle? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof ...