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

1
vote
0answers
21 views

Prove that if there are $2n$ points and $n^2+1$ straight lines connecting them, then there are at least $n$ triangles in this shape.

Proof by induction. For $n=2$, it says that if we have $2(2)=4$ points and $2^2+1=5$ lines connecting them to each other, then there are at least 2 triangles in this shape. Which is true (shown ...
1
vote
1answer
30 views

Inequalities - proof by induction

Proof by induction involving inequalities completely escapes me. I've encountered the following problem: For which non-negative integers n is $n^2 ≤ n!$? Prove your answer (by induction). So, ...
1
vote
3answers
66 views

Using mathematical induction to show that for any $n\ge$ 2 then $\prod_{i=2}^n\left(1-\frac{1}{i^2}\right)=\binom{n+1}{2 \cdot n}$

I'm trying to work through some practice problems but I've been stuck on this for god knows how long now and I've no idea where to even start. Just wondering if it would be possible for someone to ...
1
vote
1answer
69 views

Induction Proof with Combinations?

Show that for all $n\geq0$ $$\binom{n}{0}3^n+\binom{n}{1}3^{n-1}+\dotsc+ \binom{n}{n-1}3^{1}+\binom{n}{n} $$ $$= \binom{n}{0}5^n-\binom{n}{1}5^{n-1}+\binom{n}{2}5^{n-2}-\binom{n}{3}5^{n-3}+\dotsc ...
0
votes
0answers
24 views

different representations of strong induction

I've seen 2 forms of strong induction; just wondering how one follows from the other. $1) f(n_0)\wedge f(n_1)\wedge\cdots \wedge f(n_{k-1})\wedge f(n_k)\wedge \forall_n[f(n-k)\wedge ...
0
votes
3answers
79 views

Prove that $(1+2+3+\cdots + n)^2 = 1^3+2^3+3^3+\cdots + n^3$ for every $n \in \mathbb{N}$ [duplicate]

Prove that $(1+2+3+\cdots + n)^2 = 1^3+2^3+3^3+\cdots + n^3$ for every $n \in \mathbb{N}$. Proof. We will use mathematical induction. If $n = 1$, then we have $(1)^2= 1^3 = 1$. We must show that ...
2
votes
3answers
54 views

Induction Proofs - Mathematics

How do I show by mathematical induction that $2$ divides $n^2 - n$ for all $n$ belonging to the set of Natural Numbers
2
votes
2answers
58 views

How to prove $0 < a_n < 1$ by induction

I know $n \in \mathbb{N}$ and... $$ a_n = \begin{cases} 0 & \text{ if } n = 0 \\ a_{n-1}^{2} + \frac{1}{4} & \text{ if } n > 0 \end{cases} $$ Base Case: $$a_1 = ...
1
vote
1answer
26 views

Showing that a sequence (defined in terms of the previous sequence term) is increasing and bounded above

I'm stuck on this problem and I was wondering if you would be kind enough to help. The question follows: Let $x_{1} = 1$ and $x_{n}$ = $\sqrt{ 1 + 2x_{n-1}}$ for n $\geq$ 2. Show that the sequence ...
1
vote
3answers
34 views

Show that $7\mid 2^{3n} -1 \,\,\,\forall n\in \mathbb N^+$

Show that $7\mid 2^{3n} -1 \,\,\,\forall n\in \mathbb N^+$ Should I prove this by induction? If so, how should I go about it?
5
votes
4answers
66 views

Prove that $ \frac{1}{2!} + \frac{2}{3!} + \frac{3}{4!}+\cdots + \frac{n}{(n+1)!} = 1 - \frac{1}{(n+1)!}$ for $n\in \mathbb N$

I want to prove that if $n \in \mathbb N$ then $$\frac{1}{2!} + \frac{2}{3!} + \frac{3}{4!}+ \cdots+ \frac{n}{(n+1)!} = 1 - \frac{1}{(n+1)!}.$$ I think I am stuck on two fronts. First, I don't know ...
1
vote
1answer
44 views

Induction proof for Fibonacci numbers

I am trying to get a hang on the induction method for proof, but I'm still dubious of many aspect of this proof regarding its application to sequences of integers, such as the Fibonacci sequence. ...
0
votes
2answers
30 views

Prove sum of combinations

Let n and r be positive integers with n ≥ r. Prove that C(r, r) + C(r + 1, r) + ... + C(n, r) = C(n + 1, r + 1) I would like to approach with mathematical induction. However, I don't understand what ...
2
votes
3answers
101 views

How to prove this statement: $\binom{r}{r}+\binom{r+1}{r}+\cdots+\binom{n}{r}=\binom{n+1}{r+1}$

Let $n$ and $r$ be positive integers with $n \ge r$. Prove that Still a beginner here. Need to learn formatting. I am guessing by induction? Not sure what or how to go forward with this. Need help ...
1
vote
3answers
33 views

Proving this $F_{n+1} \cdot F_{n-1} - F^2_n = (-1)^n$ by induction

Where $n \in \mathbb{N}$ and $$ F_n = \begin{cases} 0 & \text{ if } n = 0 \\ 1 & \text{ if } n = 1 \\ F_{n-1} + F_{n-2} & \text{ if } n > 1 ...
0
votes
4answers
45 views

Prove $H_{2^m} \leq 1 + m$, where $H_n = \sum\limits_{k=1}^n \frac{1}{k}$

I really I am not seeing how to continue my approach, which is this. Base case: $m = 1$, so we have $H_2 \leq 2$, where $H_2 = \sum\limits_{k=1}^2 \frac{1}{k} = \frac{1}{1} + \frac{1}{2} = ...
2
votes
4answers
68 views

Equilateral triangle is cut in $4^n$ congruent equilateral smaller triangles

I have an assignment on proof by induction: Suppose n is a positive integer. An equilateral triangle is cut into $4^n$ congruent equilateral triangles, and one corner is removed. (Figure 1 ...
0
votes
1answer
23 views

Strong induction on a sequence, proving two functions are equal?

Excuse the poor title, but my understanding is still a little fuzzy. Admins feel free to change it Here is the question from the book. suppose that $f_{0}, f_{1}, f_{2}...$ is a sequence defined ...
2
votes
1answer
25 views

Induction proof with inequalities

Consider the following claim: $$5^n > 4^n + 3^n + 2^n$$ (a) For what natural numbers is this claim true? (b) Prove that your answer to (a) is correct using induction on n.
0
votes
0answers
23 views

A couple of questions about induction.

I am trying to understand the proof of the theorem 56.4 on page 387. I have asked a related question before and according to user Matt S, we use strong induction here. Where in the body of proving ...
0
votes
1answer
16 views

Lining a rectangular building square panels

I've been working on this for what feels like a lifetime now and I'm just not getting anywhere with it. I'm wondering if someone would be able to explain how to solve it for me? There is a ...
0
votes
3answers
39 views

By induction, show that for ∀n∈N, it is true that: [duplicate]

$$\sum_{i=1}^n 2^i=2+2^2+2^3+.....+ 2^n=2(2^{n}-1)$$ Any help/explanations would be REALLY appreciated. Also in the same vein: By induction, show that $$∀n∈\mathbb N: 11^{n+2} + 12^{2n+1}$$ is ...
2
votes
0answers
25 views

Confusion on particular step in this weak induction proof

I am studying for a midterm, and I came across this proof. Use mathematical induction(weak) to show that for all integers n $\geq$ 2 , if x$_{1}$, x$_{2}$, ... x$_{n}$ are strictly between 0 and 1 ...
0
votes
1answer
21 views

An induction proof in a set.

I have an induction problem that I have no idea how to start. So the question goes like this. Let $x_1=1$, $x_2=2$ and $x_n=x_{n-1} + 2x_{n-2}$. Prove that $x_n=2^{n-1}$ for all $n$ in the natural ...
-1
votes
1answer
54 views

Prove by mathematical induction [closed]

Prove by mathematical induction this expression : $$\frac 1{\sqrt{n+1}+\sqrt {n}} \lt \frac 1{2\sqrt{n}}$$
1
vote
1answer
78 views

What sets does $\mathbb{N}$ include?

My text states that the set $\{1, 2, 3...\}$, and the set $\{101, 102, 103, 104...\}$ are elements of $\mathbb{N}$. Doesn't this imply that $\mathbb{N}=\{1, 2, 3... 101, 102, 103, 104...\{1, 2, 3 ...
0
votes
1answer
28 views

induction with factorials

I need help with this please. I understand step one is to let $n=1$. step two let $ n = k$. Step three prove for $k+1$. But I would like a clear example of each... Prove $$\sum_{i=1}^n ...
1
vote
2answers
34 views

Induction of factorial

I was perusing the wikipedia page on Mathematical induction, and it mentions it's possible to prove by induction that. $\frac{n^{n}}{3^{n}}<n!<\frac{n^{n}}{2^{n}}$ for $n\geq6$ Proof for $n=6$ ...
0
votes
4answers
39 views

Use strong induction to prove that n$\leq$3$^{n/3}$ for every integer n$\geq$0

Use strong induction to prove that n$\leq$3$^{n/3}$ for every integer n$\geq$0. According to steps of Strong Induction, 1) I assume the predicate as P(n): n$\leq$3$^{n/3}$ for every integer ...
2
votes
1answer
67 views

Structural Induction, Propostitonal formulae problem

I am kind of overwhelmed by this question. Can anyone give me some hints about where to start? Propositional formulae PF are inductively defined over the Boolean constants B := {1, 0} (true and ...
1
vote
1answer
32 views

Proof by induction of whole numbers

A sequence $X_1, X_2,\dots,X_n$ is defined by: $X_1 = 1$ and $X_{k+1} = \dfrac{X_k}{X_k + 2}$ for $k\ge1$. Show by using induction that $X_n = \dfrac1{2^n - 1}$ for all $n\ge1$. So far I've showed ...
1
vote
2answers
69 views

Proving a combinatorics equality

How to prove the following? Should I use induction or something else? Let n and r be positive integers with n ≥ r. Prove that $${\binom{r}{r}} + {\binom{r+1}{r}} + · · · + {\binom{n}{r}} = ...
0
votes
2answers
31 views

A pair of questions about isomorphism between two posets.

Theorem: Let $P = (X, \le)$ be a finite total order containing n elements. Let $Q = (\{1, 2, \ldots , n\}, \le')$. Then $P \cong Q$. I have a few questions about the proof of this theorem. In my ...
1
vote
1answer
35 views

Proof by induction, inductive step help

I am having a really hard time grasping proof by induction and struggling to write consitent thorough proofs which use induction. For example, proving the following $k! \geq 3^{k-2}$ Now I ...
1
vote
3answers
44 views

Strategy for solving $7\vert2^{n+2}+3^{2n+1}$ by induction.

So I have to show the following to be true using induction $7\mid 2^{n+2}+3^{2n+1}$ This is easily checked with the case $n=0$ because $7 \mid 7$, but I assuming this holds for$n=k :$ $$7\mid ...
0
votes
3answers
22 views

Crossed induction

I have two sequences of equalities $L_n$ and $R_n$. The equation $L_{n+1}$ is true only if $R_n$ is true, and the same happens for $R_{n+1}$ $$R_n \implies L_{n+1}$$ $$L_n \implies R_{n+1}$$ How ...
1
vote
2answers
29 views

Proof by Induction: for all integers n $\ge$ 0, $12\mid8^{2n+1}+2^{4n+2}$

I'm working on a homework problem for my discrete math class, and I'm stuck. (Note: I made a post about this earlier, but I read the problem incorrectly, thus the work was wrong, so I deleted the ...
2
votes
2answers
199 views

Proof that this diagram commutes

This is an exercise in a book I'm reading: Define an $\mathbb R$-linear isomorphism $f_n : \mathbb C^n \to \mathbb R^{2n}$ by $$(x_1 + iy_1, x_2 + iy_2, \dots) \mapsto (x_1, y_1, x_2, y_2, \dots )$$ ...
1
vote
0answers
12 views

Induction for quantified statement with two discrete parameters

Given a quantified statement ∀n, n>0 (∃x, x>2k | x=2k+n) ( a subset of the natural numbers) This can logically this can be deduced as valid; however, I wish to use induction. Specifically I would ...
0
votes
2answers
29 views

Prove divisibility

We have the following proposition: $$P(n): 13^n+7^n-2\vdots 6$$. Prove $P(n)$ in two ways. I know that one of them is mathematical induction. I don't know many things about the other one, I know ...
0
votes
2answers
44 views

Proof by Induction - Math

Prove that for every integer n>=2: We have the summation of $$ \frac{1}{i(i-1)}=1-\frac{1}{n} $$ I tried the algebra with this proof, but couldn't get it. I know that you split the i-1 and the i ...
0
votes
1answer
17 views

Proof by Induction Question - as part of Russo Dye Theorem

I began with $x_{n+1} = \displaystyle \frac{x+x_n}{2}$ and did the first few iterations to find that it follows this pattern: $\displaystyle \frac{(2^n-1)x+x_0}{2^n}$. How can i show this is true for ...
0
votes
1answer
27 views

Prove by induction for$ P(x)$

$P(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0$,with $a_n\neq 0$. Using induction on $n$, prove that $P^{(n)}(x) = n!a_n$. So I start with $n=1$ but $P(x) =a_1x$ and $P^{(1)}(x)=1a_1$ are not equal because ...
0
votes
1answer
46 views

Mathematical Induction Proof 1 [duplicate]

Prove that for every integer $ n \geq 1$, we have $\displaystyle \sum_{j=1}^n j^3 = \left(\dfrac{n(n+1)}{2}\right)^2$ I know how to prove an induction proof, but I just can't get the algebra down on ...
1
vote
2answers
43 views

Proof By Induction Fibonacci Numbers

How do I prove that $$ f_{ 2n+1 } = 3f_{ 2n } + 1 - f_{ 2n-3 } $$ I'm not sure how to prove it using the defining recurrence of Fibonacci numbers.
1
vote
5answers
55 views

Prove that $2^n\geq2n-1$

Let $n\geq2$ with $n\in\Bbb N$. Prove that $$2^n\geq2n-1$$ I need to prove this using mathematical induction. This is what I've tried: $P(2): 2^2\geq2n-1 \\ P(k)\Rightarrow P(k+1) \\ P(k+1): ...
3
votes
1answer
24 views

Prove that any amount of money of at least 14c can be made up using 3c and 8c coins

I am reading a book on Discrete Mathematics, and I am on the chapter of mathematical induction. The first problem is the fairly common example of 1+2+...+n = n(n+1)/2, which I didn't have trouble ...
0
votes
1answer
36 views

a_1,a_2,a_3…..a_n of natural numbers different then 0.

I understoof the logic behind it but have no idea how to put it into words. ex: n=3 ther are 4 n sum series: 1,1,1 1,2 2,1 3 of natural numbers different then 0, will be called n sum series if the ...
0
votes
0answers
18 views

How to prove by induction/stromg induction [duplicate]

i have a question that i need to prove by induction or strong induction and I really dont know how to approach it let there be n a natural number. and a serial of numbers a1, a2,....ak of natural ...
0
votes
2answers
38 views

Weak Mathematical Induction for Modulo Arithmetic

Using Weak Mathematical Induction, I have to show that, for all integers $n \geq 1$, $8|3^{2n} -1$ I really don't know how to go about solving this problem. Currently I only have the base case and ...