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

4
votes
3answers
112 views

Prove by induction that $1+4+7+…+(3n-2) = 2n(3n-1)$

I have an exercise where I, using induction, have to prove the following: \begin{equation*} 1 + 4 + 7 + \ldots + (3n-2) = 2n(3n-1). \end{equation*} I immediately got stuck on the base case with ...
1
vote
1answer
43 views

Strong Induction Proof

Prove that $$\sum_{j=1}^n (j)(j+1)(j+2)\cdots(j+k-1) = \frac{n(n+1)(n+2)\cdots(n+k)}{k+1}$$ Hint: $P(n, k)$ is true for all pairs of positive integers $n$ and $k$ if: (a) $P(1, 1)$ is true and $P(n ...
1
vote
3answers
31 views

Solution check: Let $f_n$ be fibonacci numbers. Prove: $\sum_{k=0}^{n-1} \binom{n+k}{2k+1} = f_{2n-1}$ and $\sum_{k=0}^n \binom{n+k}{2k} = f_{2n}$

The question: Let $f_n$ be fibonacci numbers. Prove: $\sum_{k=0}^{n-1} \binom{n+k}{2k+1} = f_{2n-1}$ and $\sum_{k=0}^n \binom{n+k}{2k} = f_{2n}$ For every $n\in N$. $f_0=f_1=1$, ...
6
votes
6answers
140 views

How to prove that $2^{n+2}+3^{2n+1}$ is divisible by 7 using induction?

I want to prove that $2^{n+2}+3^{2n+1}$ is divisible by 7 using induction. My first step is replace $n$ with $1$. $2^{1+2}+3^{2(1)+1}$ $2^3+3^3$ $8+27$ $35 = 7\times 5$ The next step is assume ...
2
votes
2answers
35 views

recursive sequences bounded above and their limits at infinity

Define a sequence $\langle a(n)\rangle$ recursively by $a(1)=\sqrt{2}$ and $a(n+1)=\sqrt{2+a(n)}$ $(n>0)$. a)by induction or otherwise show that the sequence is increasing and bounded above 3. ...
0
votes
1answer
24 views

Using two dimensional mathematical induction [closed]

What are different ways in which I can use a two dimensional mathematical induction? I will also appreciate any examples of its use. By this I mean the principle that will be used when I have to ...
1
vote
2answers
38 views

Prove that the following formula is true for $n \geq 1$ by induction

Prove that the following formula is true for $n \geq 1$ by induction. $a_{n} = a_{n-1} + 4n - 3 \\ a_{n} = 2n^{2} - n + 1 \\ a_{1} = 2$ My attempt follows below. I almost succeed in proving the ...
0
votes
1answer
41 views

Prove by induction that every integer is either a prime or product of primes

Let $n$ and $d$ be integers such that $d$ is a divisor of $n$ if $n=ad$ for some integer $a$. A prime number is a integer $n>1$ that is divisible by 1 and itself. Prove by induction that every ...
-3
votes
3answers
36 views

Prove by mathematical induction for all n in N

Prove by mathematical induction that $$ 1+\frac12+\frac14+\frac18+\dotsb+\frac{1}{2^i} = 2 - \frac{1}{2^i} $$ I know the base set just stuck in the calculations for the inductive set.
2
votes
4answers
208 views

Showing a particular recurrence is constant

A sequence, $ ( a_n ) _ { n \in \mathbb{N}} $, is constructed by selecting a value of $ a_0$, and then successively forming the following elements from the equation. $$ a_n = 2- \frac12 a_ { n- 1} ...
1
vote
2answers
45 views

Show that $a_n = 2^n + 3^n .$ Strong Induction for noobs!

The Question that I have is as follows: Given that $a_0 = 2$, $a_1 = 5,$ and $ a_{n+2} = 5a_{n+1} - 6{a_n}$, show that $a_n = 2^n + 3^n .$ How do I know how many base cases to prove? And once I have ...
0
votes
4answers
85 views

Prove that $\left\lceil \frac{n}{m} \right\rceil =\left \lfloor \frac{n+m-1}{m} \right\rfloor$

On a discrete mathematics past paper, I must prove that $$\left\lceil \frac{n}{m} \right\rceil = \left\lfloor \frac{n+m-1}{m} \right\rfloor$$ for all integers $n$ and all positive integers $m$. ...
0
votes
1answer
47 views

Help with discrete mathematics proof

I am to prove $A_0\cap(\bigcup_{i=1}^n A_i) = \bigcup_{i=1}^n (A_0\cap A_i), n\ge 2$ by induction. I started out like this: Step 1: Prove that $A_0\cap(\bigcup_{i=1}^n A_i) = \bigcup_{i=1}^n ...
1
vote
1answer
21 views

How to prove $\sum_{k=1}^{n}F_k = F_{n+2}-1$ by induction when $F_n$ is the Fibonacci sequence

Let $F_n$ be the Fibonacci sequence where $F_0$ = 0 , $F_1$ = 1 and $F_n$ = $F_{n-1}$ + $F_{n-2}$. I want to prove the following by induction. $$\sum_{k=1}^{n}F_k = F_{n+2}-1$$ ...
-1
votes
1answer
63 views

Mathematical Induction - Graph Theory

Prove by induction on $n$ that $K_n$ (the complete graph on n vertices) has a Hamiltonian cycle for all $n \geq 3$. I understand this can be done not using induction, however I am very new to ...
1
vote
1answer
44 views

Explain this proof by induction? [duplicate]

$P(n)$ is the statement $n! < n^n$, where $n$ is an integer greater than $1$. I found a solution online here (https://people.cs.umass.edu/~barring/cs2... But I don't understand how they got from ...
2
votes
6answers
67 views

Inductive proof that every term is a sequence is divisible by 16

I have this question: The $n$th member $a_n$ of a sequence is defined by $a_n = 5^n + 12n -1$. By considering $a_{k+1} - 5a_k$ prove that all terms of the sequence are divisible by 16. I can do ...
1
vote
1answer
24 views

The existence of the sequence corresponding to some asymptotic sequence

The following proof of the axiom of choice by induction is obviously false: Let $(\Lambda)_{i=1, 2, \ldots}$ be an infinite sequence of nonempty sets. When $i=1$, self-evident. We will assume this ...
0
votes
0answers
8 views

proving properties of (graph) dominance defined via a system of equations

Some notions on graphs can be defined via a system of equations with values in a lattice. For example, dominance $d(v_1, v_0)$ ($v_1$ dominates $v_0$) in a graph $g$ is defined by a system $\forall ...
1
vote
1answer
33 views

What is the difference between structural induction and ordinary induction?

I know two basic differences: 1.In structural induction you can use both numeric and string datatype,while in ordinary only numeric is allowed. 2.In structural there is base case and constructor ...
3
votes
1answer
61 views

Prove by induction $n= qb+r$ for $ n\ge 0$

Let $b$ be a fixed positive integer . Prove by induction for all $ n\ge 0$ there exists $q$ and $r$ non-negative integers ( positive integers + 0) that $n= qb+r$ for $0 \le r < b $ my try its not ...
3
votes
2answers
96 views

How to prove that $9^n - 8n - 1$ is divisible by $64$ for $n\ge 0$?

My textbook provided the following proof: Base case: When $n=0, 9^n-8n-1=0=64\cdot0$, so $64\mid\left(9^n-8n-1\right)$. Induction step: Suppose that $n\in\mathbb N$ and ...
1
vote
2answers
20 views

Help with induction step of proving a recursive definition / sequence

I'm a bit of a maths noob so please bear with me with what is probably a really dumb question, but I could really do with some help - I'm self-learning at home. I'm stuck on the question below from ...
0
votes
3answers
80 views

The necessity of the axiom of induction

$\underline{First\ question}$ Let $P(n)$ be a proposition about $n$. In standard mathematical induction, we require: (1)$P(0)$ holds. (2)If $P(n)$ holds, $P(n+1)$holds. Here we use "the axiom of ...
1
vote
1answer
72 views

How do I use the principle of mathematical induction to prove whether or not $\sum_{k=1}^n (-1)^k = \frac{(-1)^n-1}2$ is a true statement?

For all n elements of Natural Numbers,$\sum_{k=1}^n (-1)^k= \frac{(-1)^n-1}2$. I proved p(1) to be true : $\sum_{k=1}^1 (-1)^k = (-1)^1 =-1$. And $\frac{(-1)^1-1}2 = \frac{(-2)}2 = -1$ So P(1) ...
0
votes
3answers
49 views

Use mathematical induction to prove $ (2n)!\geq 2^n(n!)^2$ for $n \in \mathbb{N}$

I am trying to use mathematical induction to prove $$(2n)!\ge2^n(n!)^2\quad\text{for }n\in\mathbb{N}$$ I am stuck at the $n=k+1$ point.
0
votes
1answer
25 views

Proving that there exists a horizontal chord with length $1/n$ for a continuous function $f: [0,1] \to \mathbb R$

Given a continuous function $f: [0,1] \to \mathbb R$ and that the chord which connects $A(0, f(0)), B(1, f(1))$ is horizontal then prove that there exists a horizontal chord $CD$ to the graph $C_f$ ...
8
votes
1answer
57 views

Is there a standard name for this “continuous induction” principle?

I am working on a paper, and I want to prove that some statement $P(x)$ holds for every value of a parameter $x \in [0,\infty)$. I plan to proceed as follows: Show that $P(0)$; Show that if $P(x)$ ...
3
votes
6answers
85 views

Using induction prove $(n^3)-n$ is divisible by 3 whenever n is a positive number.

I am not sure if I am doing this right, but I have this: There exists an integer $k$. $2k =$ positive number $(2k)^3 - 2k$ [*And this is where I get lost. How does one prove this?]
0
votes
0answers
69 views

Why is $y + 1$ infinite?

This is related to SO question : http://stackoverflow.com/questions/30150877/why-does-this-cause-ghci-to-hang but I'm having difficulty understanding why Haskell enters an infinite loop but since ...
3
votes
8answers
114 views

Proving that $12^n + 2(5^{n-1})$ is a multiple of 7 for $n\geq 1$ by induction

Prove by induction that $12^n + 2(5^{n-1})$ is a multiple of $7$. Here's where I am right now: Assume $n= k $ is correct: $$12^k+2(5^{k-1}) = 7k.$$ Let $n= k+1 $: $$12^{k+1} + 2(5^k)$$ ...
3
votes
2answers
42 views

simplifying equations

I have been trying to study analysis of algorithms with mathematical induction yet I found my algebra skills are very poor. So now I began restuddiing algebra (factoring, destributive property, ...
3
votes
3answers
45 views

Prove that Euclid's algorithm computes the GCD of any pair of nonnegative integers

I've been struggling with a basic exercise involving Euclid's algorithm and mathematical induction. Given the following definition of the Euclid's algorithm (in Java): ...
1
vote
1answer
34 views

How to show $(1+a)^n<1+2^n a$ for all $n\in\mathbb N$ and $a\in (0, 1)$?

There is an induction problem which is baffling me. I'm supposed to use induction to show the inequality $$(1+a)^n< 1+2^n a,$$ for all $n\in\mathbb N$ and $a\in (0, 1)$. I guess there must be some ...
0
votes
1answer
55 views

Show that there exists a unique function with a certain property

I'm trying to prove the following theorem: "Let $~f: \mathbb{N} \times \mathbb{N} \to \mathbb{N}~$ be a function, and let $~c~$ be a natural number. Show that there exists a unique function $~a: ...
0
votes
2answers
32 views

Using induction prove $\sum\limits_{k=1}^n\dbinom{k}{k-1}$=$\binom{n+1}{n-1}$

$\sum\limits_{k=1}^n\dbinom{k}{k-1}$=$\binom{n+1}{n-1}$ We are supposed to use induction to prove this inequality. After the base case, I tried to use the definition $\binom{n}{k} = ...
8
votes
6answers
256 views

Proof without using induction [duplicate]

How to prove that $$1^2+2^2+...+n^2=\frac{n(n+1)(2n+1)}{6}$$ without using induction. If we don't know the right side of this expression, how to get right expression. I tried with partial sums and ...
2
votes
1answer
61 views

how to prove by induction the $ (1+x)^{n}>1+nx+nx^2$

Prove by induction the formula $ (1+x)^{n}>1+nx+nx^2$ for $x>0$ real number and $n\ge 3$ my try : multiply both sides by $(1+x)$ gives $ (1+x)^{n+1}>1+(n+1)x+(2n+nx)x^2$ have I done ...
1
vote
2answers
70 views

Prove that if $\sum \limits_{k=1}^{n} x_n=1$ then $\sum \limits_{k=1}^{n} x_n^2 \geq {1 \over n}$

Prove that if $\sum \limits_{k=1}^{n} x_n=1$ then $\sum \limits_{k=1}^{n} x_n^2 \geq {1 \over n}$ where $\{x_k\}_1^n$ are real numbers which are not all the same. I tried to prove it by induction. ...
1
vote
2answers
31 views

Is this inductive big O proof possible / Does this question make sense?

Prove that $\sum_{i=j}^k \frac 1i$ is $O(\ln(k)-\ln(j-1))$ using induction for all $i$. The way I understand this question, it's nonsense - $i$ is the iteration variable, not something that can be ...
0
votes
1answer
32 views

How to prove this by induction

Prove by induction the following equality : $\ 1-4+9-16+\cdots+(-1)^{n+1} n^2 = (-1)^{n+1}(1+2+3+\cdots+n) $ I don't know what to do in this case, I know what to do in general but can do this one
1
vote
3answers
38 views

Question regarding proving by induction

I am struggling with a math problem I have been assigned. The problem is as follows: Let $X_1 = -3$ and $X_2 = 0$. Given that for every natural number $n \geq 2, X_{n+1} = 7X_n - 10X_{n-1}$, prove by ...
5
votes
1answer
60 views

Partition onto subsets at the same sum

Positive integers $ a_1, a_2,\ldots, a_n $ such that $ a_k\leq k $ and the sum of all these numbers is even and equal to $ 2S $. Prove that the number can be divided into two groups, the amount of ...
0
votes
2answers
68 views

Using induction to prove letter arrangement

There are n letters written to different people, and envelopes correspondingly addressed. The letters are mixed before being sealed in envelops, the effect being to make n!allocations of letters to ...
4
votes
8answers
155 views

Proving that $5^n-1$ is divisible by $4$ for $n\geq 0$ by induction

I hope this is not counted as a duplicate, as I would like to know if my proof is valid: $P(n): 5^n - 1$ is divisible by $4$ for $n \ge 0$. Base Step: $P(0): 5^0-1 = 1-1 = 0 = 0\times 4$. Induction ...
-1
votes
2answers
77 views

What are the prerequisites required if I have to do induction to prove a certain theorem

I have always been fascinated by mathematical induction. The idea of induction is itself such a great analogy. But sometimes induction makes me feel that it is very messy. My professor keeps on saying ...
0
votes
4answers
42 views

Show that the sequence is monotone and bounded.

Show that the sequence defined by $a_1=1$ and $a_n=\sqrt{3+a_{n-1}}$ for $n>1$ is monotone and bounded. Then find the limit of the sequence. I'm supposed to do this using induction. I'm usually ...
1
vote
3answers
65 views

How to prove a Fibonacci inequality using Strong Induction?

Using strong induction I am trying to prove that $$F_n \geq \left(\frac{1+\sqrt{5}}{2}\right)^{n-2} \text{ for all } n \geq 2$$ for the Fibonacci Sequence defined by: $F_0 = 0$, $F_1 = 1$, and $F_n ...
1
vote
1answer
36 views

Induction Clarification

I had this problem: Is it always necessary to go from n to (n + 1) or from (n - 1) to n in the inductive hypothesis? Is the "direction" always important? Here is my solution to one such proof, which ...
1
vote
2answers
59 views

How to prove that the statement $ 4+10+16 + \cdots + (6n-2) = n(3n+1)$ for all $n \ge 1$ using mathematical induction?

I know you begin by establishing that it is true for $n=1$ which gives $6(1)-2 = 1(3\cdot1\cdot+1)$. Then I replace each $n$ for a $k$, and I suppose that is true for $6k-2=k(3k+1)$. But then the ...