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

0
votes
1answer
42 views

Limit of $a_{n+1}= \frac{n}{n+1} a_n$

I think that this sequence $$a_{n+1}= \frac{n}{n+1} a_n$$ can be rewritten as $$a_n= \frac{1}{n+1}a_0.$$ Therefore the limit should be $0$. But my proof by induction turns out wrong. Is my idea ...
0
votes
1answer
50 views

How can I prove this statement about square root?

Introduction In computer science there is a field called Formal Methods and Specifications. In this field software designers design softwares by specifying their functionalities in formal methods, ...
4
votes
2answers
40 views

What are statements about the natural numbers where induction is impossible or unnecessary to prove?

I'm looking for statements like "for all natural numbers, ____" where induction would be impossible or unnecessarily complicated. This is for pedagogical reasons. When students first learn induction, ...
0
votes
0answers
23 views

Demonstration of exponentiation with induction

How can you demonstrate that $a^0 = 1$ and that $a^{-n} = (1/a)^n$ using the principle of mathematical induction?
2
votes
1answer
34 views

How many Fibonacci Numbers are in the sequence

I have $I_n = \{2^n + 1, 2^n + 2, 2^n + 3, \dots , 2^{n+1}\}$ and I am trying to prove using induction how many Fibonacci numbers are there. First, the length of $I_n$ is $|I_n| = 2^n$ then for $F_0 ...
1
vote
3answers
89 views

Prove $\frac{1}{n} =\frac{1}{n+1}+\frac{1}{n(n+1)}$ for all integers $n\in\Bbb Z$

I'm pretty sure that we need induction, since it's the format I had to use for previous problems similar to this (it isn't specified that it HAS to be an inductive proof, either, if there is another ...
0
votes
0answers
55 views

Using induction to prove the “hockey stick theorem”

The question we were given was (where $^nC_c$ is $n$ choose $c$): Show, using induction and the fact that $^nC_c + ^nC_{(c+1)} = ~^{(n+1)}C_{(c+1)}$, the "hockey stick theorem": the sum from $k=c$ ...
5
votes
3answers
76 views

Using induction to prove that $n^2 > n + 1$ for $n\geq2$

Use mathematical induction to prove that $n^2 > n + 1$ for all $n\geq2.$ I have proved that it is true for the initial case $n=2$ as $4>3$, and have assumed the statement to be true for $k^2 ...
0
votes
0answers
12 views

Prove Ackermann's function by induction

I have to prove the following property $$A(x,y)>x$$ of Ackermann's function. Do we do the following? We will show that $$A(x, y) \geq A(0, x+y)$$ by induction on $k=x+y$. Base case: For $k=0$ ...
0
votes
1answer
22 views

Proving $F_n \ge (\frac{1}{2}(1+\sqrt{5}))^{n-2}$ for $n \in \mathbb{N}_{>1}$ when $F_n$ is the nth Fibonacci number

Let $F_n$ be defined as the nth Fibonacci number. Prove that $F_n \ge (\frac{1}{2}(1+\sqrt{5}))^{n-2}$ with $n \in \mathbb{N}_{>1}$ My approach thus far was to use induction over $n$. ...
-1
votes
1answer
33 views

Is there an easier way to prove this induction?

Given that $u_1=1$, $u_{r+1} = \frac{2u_r-1}{3}$ Prove using induction that $u_n = 3(\frac{2}{3})^n-1$ Step 1: prove that $u_1=3(\frac{2}{3})^1-1$ $3(\frac{2}{3})^1-1$ $3(\frac{2}{3}) - 1$ $2-1$ ...
2
votes
2answers
41 views

Prove this binomial identity using induction

prove this identity: $(1-x)^{-k} = \sum\limits_{i>=0} \binom {n+k-1} {k-1} x^n $ using induction. Verification for k=1 is trivial. assuming k= i, proving the identity when k=i+1 is something i ...
0
votes
1answer
23 views

Is this a proof that recursive definition of functions indeed defines a function?

Someone asked me how you prove that defining a function recursively actually defines a function, and then I tried to rigorously prove it. Is it right? Let $\mathbb{N}=\{0,1,2,\dots\}$. For any ...
2
votes
6answers
97 views

Prove that $7$ divides $1 + 2^{(2^n)} + 2^{(2^{n+1})}$ by induction

Prove that $7$ divides $1 + 2^{(2^n)} + 2^{(2^{n+1})}$ by induction. I ran into the above problem. The base case $n=1$ gives $21$ which is divisible by $7$. Now assume it is true for $n$. Then for ...
4
votes
3answers
108 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 ...
-2
votes
0answers
25 views

Fibonacci Sequence $f_{2n+1} = f^2_n + f^2_{n+1}$ Strong Induction Proof [closed]

With the Fibonacci sequence $f_n$ defined as $f_n = f_{n-1} + f_{n-2}$ for $n\ge2$ with $f_0 = 0$ and $f_1 = 1$, prove the following using strong induction for any $n\in N$: $$ f_{2n+1} = f^2_n + ...
1
vote
1answer
42 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 ...
0
votes
3answers
29 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$, ...
5
votes
7answers
121 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 ...
1
vote
2answers
29 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
21 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
37 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
31 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
205 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
82 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
45 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
54 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
42 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
59 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
18 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
6 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
54 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 ...
1
vote
2answers
69 views

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

My textbook provided the following proof: http://imgur.com/5y5KbJ2 What i don t understand is how the equation goes from $= 9^{n+1} - 8n - 9 $ to $= 9^{n+1} - 72n - 9 + 64n$
1
vote
2answers
17 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
2answers
66 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 ...
-2
votes
5answers
37 views

Mathematical induction (Sequence) [closed]

How to prove this by mathematical induction? $1+\frac{1}{2}+(\frac{1}{2})^2+(\frac{1}{2})^3+...+(\frac{1}{2})^n=2(1-(\frac{1}{2})^{n+1})$.
1
vote
1answer
71 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
21 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
56 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
78 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
61 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
104 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
36 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
33 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 ...