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
3answers
42 views

using mathematical induction problem with n variable as exponent

I am a first year Math student and I am looking at problem in my text book which does not have any answers and I have completely no idea how to do this paticular problem. Show, using mathematical ...
6
votes
4answers
289 views

In-Depth Explanation of How to Do Mathematical Induction Over the Set $\mathbb{R}$ of All Real Numbers?

     I've seen in the answers to a few different questions here on the Mathematics Stack Exchange that one can clearly do mathematical induction over the set $\mathbb{R}$ of ...
1
vote
2answers
19 views

Proving $\sum_{r=1}^n(6r-2)=n(3n+1)$ by induction

A series is defined by $\sum\limits_{r=1}^n(6r-2)$. Use the method of induction to prove that $S_n=n(3n+1)$. I am at the induction step but I am struggling to rearrange $k(3k+1)+6(k+1)-2$ into the ...
3
votes
2answers
80 views

Proving that $\sum_{i=2}^n(5i-4)=\frac{n(5n-3)-2}{2}$ for all $n\geq 1$ by mathematical induction

I have this question: Show, using mathematical induction, that for all natural numbers $n$, $$6 + 11 + 16 + 21 + \cdots + (5n-4) = \frac{n(5n-3)-2}{2}$$ I am confused in that that question states ...
-1
votes
2answers
57 views

Prove $10^{n-1}\le a \lt 10^n$

$$ \forall a \in \mathbb{N}: \quad a = a_{n-1}\times10^{n-1} + a_{n-2}\times10^{n-2} + \dots + a_1\times10 + a_0 \\ a_{n-i} \in \{0;1;2;3;4;5;6;7;8;9\}; \quad a_{n-1} \neq 0 $$ We say that $a$ has ...
3
votes
2answers
193 views

Proof by induction that $x_n>2$ where $x_{n+1}=\frac{2x_n^2 +4x_n -2}{2x_n+3}$

The sequence $x_1$ $x_2$ $x_3$..... is such that $x_1=3$ and $$x_{n+1}=\frac{2x_n^2 +4x_n -2}{2x_n+3}$$ Prove by induction that $x_n>2$ for all $n$. First I proved the base case using $n=1$ as ...
4
votes
4answers
112 views

Proving that $6^{2n+1} + 1$ is divisible by $7$ for $n\geq 1$ by induction

How should I go about solving a problem like this using induction? Would I: First test $(n = 1)$ so that $6^{2(1)+1} + 1 = 6^3 + 1 = 217/7 = 31$. Then assume $(n = k)$ so that you have $6^{2(k) + 1} ...
1
vote
2answers
102 views

Trying to prove $2( \sqrt{n+1}-\sqrt n )< \frac{1}{\sqrt n}<2( \sqrt{n}-\sqrt {n-1})$ and use this to prove… [duplicate]

I am trying to prove this $2( \sqrt{n+1}-\sqrt n )< \frac{1}{\sqrt n}<2( \sqrt{n}-\sqrt {n-1})$ if $n \ge 1$ and using this to prove $2\sqrt{m}-2<\sum^m_{n=1} \frac{1}{\sqrt n}<2( ...
0
votes
2answers
43 views

How to prove the Archimedean property?

The archimedean property states that $$\boxed{~\forall~ ~a,b\in \mathbb{Z}^+~ \exists ~n~|~na\geq b~}$$ I started with disproving .. Suppose $\forall ~\{n,a,b\} \subset \mathbb{Z}^+ , \text{na ...
0
votes
1answer
122 views

Mathematical Induction. Horses made me question my understanding [duplicate]

I recently read about the false inductive proof that all horses are the same colour. There are some mathSE threads about this already (MathSE_thread_1, MathSE_thread_2). After reading this, I now ...
6
votes
5answers
108 views

Inductively prove that any natural number $\ge 12$ can be written as the sum of 4s and 5s

I can intuitively see why this is true: Let us assume $n = \alpha \times 4 + \beta \times 5$ with $\alpha,\beta \in \mathbb{N} \cup \{0\}$. $\forall n \in \mathbb{N} \cup \{0\}$: $n \div 4$ will ...
3
votes
3answers
30 views

Having problem in last step on proving by induction $\sum^{2n}_{i=n+1}\frac{1}{i}=\sum^{2n}_{i=1}\frac{(-1)^{1+i}}{i} $ for $n\ge 1$

The question I am asked is to prove by induction $\sum^{2n}_{i=n+1}\frac{1}{i}=\sum^{2n}_{i=1}\frac{(-1)^{1+i}}{i} $ for $n\ge 1$ its easy to prove this holds for $n =1$ that gives ...
3
votes
1answer
44 views

Proof by induction from Spivak's calculus ch 2- 3b

I was cracking my head over the following proof (by induction) from Spivak's calculus. Givens: $ \binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k} $ and $ n \ge k $ Task: Proof by induction that $ ...
0
votes
1answer
42 views

Prove using mathematical induction that $n^2 > n+1$ for all $n \ge 2$

I have proved for the initial case $P(2)$ that this is true, but I'm stuck at substituting in $n=k+1$, $(k+1)^2 > (k+1)+1$ = $k^2 + 2k + 1 > k+2$, where do I go from here or have I made a ...
0
votes
1answer
60 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
105 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, ...
13
votes
7answers
253 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
28 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?
4
votes
1answer
46 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
108 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 ...
1
vote
0answers
94 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
93 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
40 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
33 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
34 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
65 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
28 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 ...
3
votes
6answers
107 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
122 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
62 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
39 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
161 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
106 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
73 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 ...
2
votes
2answers
55 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
303 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
38 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
212 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
58 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
109 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
52 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
30 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
129 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
47 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
110 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
35 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
11 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
69 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 ...
2
votes
1answer
78 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
257 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 ...