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
39 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
51 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
29 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
34 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
44 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
62 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
55 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
68 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
27 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
41 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
35 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
57 views

Proof by Induction Algorithm [closed]

I am stuck on trying to prove this algorithm using mathematical induction. ...
0
votes
3answers
42 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
80 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
12 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
72 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
39 views
+50

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
45 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
23 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
40 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
35 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
37 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
17 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
20 views

Prove summation by Induction

Prove this by induction n ∑ i(i!) = (n+1)!-1 i=1 So I wrote: ...
3
votes
1answer
47 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
37 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 ...
5
votes
1answer
29 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
28 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
40 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
49 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
85 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
123 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
16 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
24 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 ...
0
votes
3answers
47 views

Prove that $\sum \frac{1}{2^n} = 1- \frac{1}{2^n}$ [closed]

Prove that $$\Large\sum\limits_{k=1}^n \frac{1}{2^k} = 1 - \frac{1}{2^n}$$ for all $n$. I am apparent not good enough at algebra for this one.
-1
votes
0answers
23 views

Proof by Induction (Permutations)

Let A be a set with n elements. Let S(A) be the set of all permutation of A; that is, S(A) is the set of all bijective functions from A to A. prove by induction that S(A) contains n! elements.
5
votes
0answers
35 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 ...
0
votes
2answers
19 views

Let $A_1, A_2, \ldots, A_n$ be sets (where $n \ge 2$). Suppose for any two sets $A_i$ and $A_j$ either $A_i \subseteq A_j$ or $A_j \subseteq A_i$

Let $A_1, A_2, \ldots, A_n$ be sets (where $n \ge 2$). Suppose for any two sets $A_i$ and $A_j$ either $A_i \subseteq A_j$ or $A_j \subseteq A_i$. Prove by induction that one of these $n$sets is a ...
1
vote
2answers
61 views

Prove by induction $1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{2^n} \ge 1 + \frac {n}{2}$

Prove by induction $1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \ldots + \frac{1}{2^n} \ge 1 + \frac {n}{2}$ I can't explain in words how the left hand side of the equation is achieved soI shall ...
0
votes
2answers
44 views

Proofs for $g(x)=e^{-1/x^2}$ when $x\neq0$, and $g(x)=0$ when $x=0$

Sorry for the non-descriptive title - the question is a bit long. I have $g(x)$ as in the title, and we proved previously that $g'(0)=0$ using L'Hôpital's rule. Now I must show by induction that ...
1
vote
4answers
44 views

proof by induction: sum of binomial coefficients

Question: Prove that the sum of the binomial coefficients for the nth power of $(x + y)$ is $2^n$. i.e. the sum of the numbers in the $(n + 1)^{st}$ row of Pascal’s Triangle is $2^n$ i.e. prove ...