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

2
votes
4answers
53 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} ...
13
votes
7answers
157 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
2answers
974 views

Number of nodes in binary tree given number of leaves

How would I prove that any binary tree that has n leaves has precisely $2n-1$ nodes ? Given that a binary tree is either a single node "o" or a node with the left and right subtrees contains a binary ...
-1
votes
4answers
90 views

Proof using induction: $15n^2 \leq 2^n$ [on hold]

How to prove this using induction: $15n^2 \leq 2^n$ (with $n \geq 11$) Thanks for your help!
0
votes
2answers
71 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
33 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 ...
6
votes
4answers
79 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 ...
0
votes
1answer
52 views

Mathematical Induction. Horses made me question my understanding

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 ...
3
votes
3answers
25 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
30 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
291 views

Induction to prove regular expression

Prove that is if S and T are any regular expressions over the one-letter alphabet, (for example: Σ = {a}), and if n is any natural, then the languages (ST)^n and (S^n)(T^n) are equal. I have to use ...
0
votes
1answer
38 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 ...
5
votes
1answer
52 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 ...
1
vote
4answers
2k views

Prove that $ n^3 + 5n$ is divisible by 6 for all $n\in \textbf{N}$ [duplicate]

Prove that $ n^3 + 5n $ is divisible by 6 for all $ n \in \textbf{N} $. I provide my proof below.
4
votes
4answers
74 views

Prove that $1^3 + 2^3 + 3^3 +\cdots+ n^3 = \frac14n^4 + \frac12n^3 + \frac14n^2$

I have to prove that this is true using mathematical induction. I have this: for every $n \in \mathbb N$: $1^3 + 2^3 + 3^3 + ... + n^3 = \frac 14n^4 + \frac 12n^3 + \frac 14n^2$ for $n = 1: 1^3 = ...
1
vote
1answer
47 views

Induction proof of the area of a square

English is not my first language, so I'm sorry if I'm not very clear. I can clarify any question you have. Also, I don't know how to use that math formatting so I apologize for it. I was asked to ...
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 ...
2
votes
1answer
36 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 ...
0
votes
1answer
53 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, ...
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?
5
votes
3answers
79 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 ...
1
vote
3answers
92 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
56 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$ ...
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$. ...
30
votes
14answers
3k views

Why doesn't mathematical induction work backwards or with increments other than 1?

From my understanding of my topic, if a statement is true for $n = 1,$ and you assume a statement is true for arbitrary integer $k$ and show that the statement is also true for $k + 1,$ then you prove ...
5
votes
5answers
637 views

Given $n \in \mathbb N$, prove $\sum^n_{k=0}(-1)^k {n \choose k} = 0$

I tried to solve it using induction, but that got me no were, in the middle of the equation stat appearing ks that I don't see how to get out of the equation. I think the easiest way to prove it, it's ...
5
votes
7answers
126 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
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$ ...
0
votes
1answer
48 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: ...
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 ...
2
votes
2answers
46 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
24 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
100 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
111 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 ...
5
votes
8answers
156 views

Prove with induction that $11$ divides $10^{2n}-1$ for all natural numbers.

$$10^{2(k+1)}-1 = 10^{2k+2}-1=10^{2k}\cdot10^{2}-1$$ I feel like there's something in that last part that should make it work, but I can't grasp it. Am I missing something obvious? Am I going in the ...
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$, ...
-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 + ...
2
votes
2answers
71 views

Proof by induction of a Fibonacci relation [duplicate]

We know: $F_0 = 0$ $F_1 = 1$ $F_i = F_{i-1} + F_{i-2}$ for $i \geq 2$ Prove by induction: $F_i = \dfrac{\phi^i-{\phi^{*}}^i}{\sqrt{5}}$ where $\phi = (1+\sqrt{5}) / 2$ and $\phi = (1-\sqrt{5}) / ...
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
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 ...
22
votes
7answers
3k views

Why $a^n - b^n$ is divisible by $a-b$?

I did some mathematical induction problems on divisibility $9^n$ $-$ $2^n$ is divisible by 7. $4^n$ $-$ $1$ is divisible by 3. $9^n$ $-$ $4^n$ is divisible by 5. Can these be generalized as $a^n$ ...
2
votes
4answers
206 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
votes
1answer
56 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 ...
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.
0
votes
4answers
83 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$. ...
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
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 ...