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 meant ...

learn more… | top users | synonyms

3
votes
3answers
83 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
28 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
39 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
69 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
70 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
63 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
126 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 ...
2
votes
4answers
73 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
51 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
200 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
70 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
38 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
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
40 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
27 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
vote
1answer
80 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
31 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
1answer
40 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
52 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
77 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
39 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
81 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
33 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
50 views

How to approach the inductive step in proving statements like $k! \geq 3^{k-2}$

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
48 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
24 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 ...
2
votes
2answers
42 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
203 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
17 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
31 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
48 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
18 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
51 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
50 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
56 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
47 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
40 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
19 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
60 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 ...
1
vote
2answers
830 views

Prove by induction the predicate (All n, n >= 1, any tree with n vertices has (n-1) edges).

I'm stuck on this problem, posting my progress so far below. I've looked at similar questions here and here, but neither seem to directly prove the predicate by induction, with a base case followed by ...
0
votes
4answers
73 views

How to show $a_n = \frac{n+1}{n-1}$ is strictly decreasing by induction?

I can show this fact otherwise, but I can't seem to figure out the simple algebra to prove it by induction...Could someone provide a hint? I just need a push in the right direction. It seems too ...
2
votes
2answers
96 views

Mathematical Induction Proof - Exponent with n in denominator

Use mathematical induction to prove the following: $$\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+...+\frac{n}{2^n}=2-\frac{n+2}{2^n}; n ∈ N $$ I am having trouble figuring out how to solve this with an ...
1
vote
1answer
32 views

Another quick induction question for a recursively defined sequence (with closed form formula given)

I was given: A sequence is defined recursively by $a_0 = 1$, $a_1 = 4$, and for $n\ge2$, $a_n = 5a_{n-1} - 6a_{n-2}$. Use induction to prove that the closed form formula for $a_n$ is $a_n = ...
0
votes
2answers
47 views

mathematical induction, prove the expression with summation

how to prove by mathematical induction the below expression: can someone help me by proving it by the standart way
1
vote
1answer
42 views

Proof by induction that x_n < 2^n

Define $x_1=x_2=x_3=1$ and $$x_{n+1}=x_n+x_{n-1}+x_{n-2}$$ for $n≥3$. Prove that $$x_n<2^n \qquad ∀n\in\mathbb N$$ I have shown the base case and supposed the result in the inductive case. Then, ...
1
vote
4answers
51 views

Alternative proof for $\forall n\in\mathbb N (n\ge 6 \Rightarrow \exists a,b\in\mathbb N : n=3a+4b)$

Can I use only strong induction in order to prove $$\forall n\in\mathbb N (n\ge 6 \Rightarrow \exists a,b\in\mathbb N : n=3a+4b)$$ Is there any other option?
0
votes
1answer
38 views

Prove inequality holds

Show that: $\displaystyle 2! \cdot 4! \cdot... \cdot(2n)!>[(n+1)!]^n $ for $n>1$ where $n$ is natural I tried by induction but I stuck when I have to show that: $(2n+2)!>(n+2)!(n+2)^n$
0
votes
1answer
74 views

Prove by induction on a sequence

We have $$ n \in R $$ And an arithmetic sequence of natural numbers different than 0 that the sum of all its members = n $$ a_1,a_2,...,a_k $$ $$ a_1+a_2+...+a_k = n $$ I need to prove by ...