Induction in general is the inference from the particular to the general. Mathematical induction is not true induction, but is a form of deductive reasoning. Its most common use is induction over well ordered sets, such as natural numbers, or ordinals. While induction can be expanded to class ...

learn more… | top users | synonyms

-1
votes
0answers
22 views

Induction method(theory of computation). [on hold]

Prove by induction that |A*B|=|A|*|B|,for all set of A&B.
4
votes
4answers
97 views

The number $(3+\sqrt{5})^n+(3-\sqrt{5})^n$ is an integer

Prove by induction that this number is an integer: $$u_n=(3+\sqrt{5})^n+(3-\sqrt{5})^n$$ Progress I assumed that it holds for $n$ and I tried to do it for $n+1$ but the algebra gets quite messy and ...
1
vote
0answers
17 views

Reference for $F$-algebras and induction?

I've been learning about $F$-coalgebras and coinduction from this fantastic paper, which has really helped me get a feel with its many examples. I'm starting to struggle with reconciling the ...
0
votes
2answers
26 views

Proof of the inequality $F_i<(5/3)^i$ for the Fibonacci numbers

The example states: As an example, we prove that the Fibonacci numbers, F0 = 1, F1 = 1, F2 = 2, F3 = 3, F4 = 5,..., Fi = Fi - 1 + Fi - 2, satisfy Fi < (5/3)i, for all i >= 1. To do this, we ...
0
votes
1answer
23 views

Induction Problem Number of Tiles on Floor

I took a discrete math course about a year ago, and I recently decided to crack open my book again as a refresher on induction proofs and problems. I ran across this problem, which I didn't remember ...
-1
votes
1answer
52 views

Proof by Induction [Number Theory by George E. Andrews 1-1 #2] [duplicate]

I am to use mathematical induction to prove that: $$1^3 + 2^3 + 3^3 + \cdots + n^3 = (1 + 2 + 3 + \cdots + n)^2 $$
1
vote
3answers
52 views

Showing that $\sum\limits_{k=2}^n {k\choose2} = {{n+1}\choose 3}$ for integers $n\geq 2$

I'm trying to prove that $\sum\limits_{k=2}^n {k\choose2} = {{n+1}\choose 3}$ for integers $n\geq 2$. I figured induction was the way to go, so I tried. This is what I've accomplished so far: Proved ...
1
vote
1answer
40 views

Maximum and average number of inversions in array by induction

Just for your information, an inversion in an array $a$ is any ordered pair of points $(i, j)$ where $i < j$ and $a_i > a_j$. I can prove the maximum and average number of inversions in an ...
27
votes
6answers
3k views

Prove that the 25 people can be seated in this way

5 mathematicians, 5 biologists, 5 chemists, 5 physicists, and 5 economists sit around a large round table. Prove that the 25 people can be seated such that, if A and B are two different people with ...
0
votes
0answers
12 views

Math Bases of Comparison and Association [on hold]

My question is about the cognitive phenomenon of intuitive pattern-matching or association by similarity / dissimilarity. Imagine a situation where a person has a particular experience, which might ...
0
votes
1answer
39 views

Prove if n<m there is at least one [(n/m)]?

Suppose there are n programmers in m cubicles. Prove that there must be at least one cubicle containing at least [(n/m)] programmers. Note: I was not able to find the right sign [ is returning first ...
3
votes
2answers
66 views

Limit of a sequence of averages (three variables)

Let $a_0 = 0$, $a_1 = 0$, $a_2=1$ and for $n>2$, $a_n = \dfrac{a_{n-1}+a_{n-2}+a_{n-3}}{3}$. Consider $\lim\limits_{n \to +\infty} a_n$. Using a python script I found that $a_n$ tends to ...
1
vote
1answer
29 views

For every $n$ there exists $m$ such that $m/n$ is an upper bound but $(m-1)/n$ is not

This is a problem discussed in Analysis 1 by Terence Tao. $E$ is a non-empty set of Real numbers. $ n\geq 1$, $L,K$ are two integers such that $L<K$. Let $\frac{L}{n}$ is not an upper bound of ...
2
votes
4answers
70 views

Prove that $133$ divides $11^{n+1} + 12^{2n−1}$ for all $n > 1$? [duplicate]

I have tried this question so hard but still stuck here. It seems like easily provable if all $n$ are all positive numbers but in this question, the $n$ is bigger than $1$. original question : prove ...
1
vote
1answer
59 views

Induction on prime numbers

To dive straight into the question: is there a form of induction which works on prime numbers? I've thought, and while I'm pretty sure it can be done om numbers such as even numbers or numbers ...
2
votes
2answers
68 views

Show that $(n+1)^{n+1}>(n+2)^n$ for all positive integers

Show that: $(n+1)^{n+1}>(n+2)^n$ holds for all positive integers I tried using induction: for $n=1$ we have 4>3 then for $n+1$ we have to show that $(n+2)^{n+2}>(n+3)^{n+1}$ and here I ...
0
votes
1answer
32 views

how to prove using induction that sum of terms?

Prove that $\displaystyle\sum\limits_{i=1}^{k}\left(\dfrac{1}{(2i-1)}\dfrac{1}{(2i+1)}\right) = \dfrac{k}{(2k+1)}‎‎$ My Base of Induction is to check that it is true for i=1, so: ...
1
vote
1answer
51 views

Proof of equation $\sum_{k}{n\brack k}a_k = n!2^{n-1}$ by induction

I'm trying to prove to following equation: $$\sum_{k=0}^{n}{n\brack k} a_k = n!2^{n-1};\ \ \ n\ge 1$$ $a_n$ - number of ordered partition of set. We have following recursion dependencies: $a_n = ...
0
votes
1answer
29 views

Readings on more general/abstract notions of induction related to logic

Can someone suggest references to understand the more general/abstract concept of induction? Specifically, I am trying to justify to myself what is called induction on the "complexity of a ...
1
vote
1answer
27 views

Induction proof for continued fractions

Recently while preparing for a maths test, I got this question in a book: Let $a(n) = 3 + \cfrac{1}{3+\cfrac{1}{3+\cfrac{1}{3+\cdots }}}$ till $n$ terms. Prove that $a(n) \cdot a(n-1)=3a(n-1)+1$ ...
-2
votes
2answers
56 views

What's wrong with this induction based proof?

Claim: $\forall x \in \mathbb{R^+} ,$ $ x^n=1 $ $where$ $ n\in \mathbb{N}$ Proof by induction on n: Basis step: $\forall x \in \mathbb{R^+} ,$ $ x^0=1 $ Induction Step: Let this holds for all ...
0
votes
2answers
25 views

Help me find the wrong in this inductive method proof?

Problem: Prove that: In a classroom with n student, if there is a girl student, all students of this class are girl. Solving: Let f(n) is the clause: In the class, if there is 1 girl student, all of ...
2
votes
1answer
63 views

Equivalence between “mathematical induction” and “transfinite induction” for natural numbers?

The "principle of mathematical induction" says that for a subset $S$ of $\omega$ (where $\omega$ is the set of all natural numbers), if $0 \in S$ and $n \in S \implies n^+ \in S$, then $S = \omega$. ...
-2
votes
2answers
53 views

Proof by Induction Problem [closed]

There are n islands with n bridges connecting pairs of islands (where n $\ge$ 2). Prove that some sequence of distinct bridges forms a loop. Hint: Argue by contradiction: suppose there is no loop. ...
0
votes
0answers
36 views

Proof Strategy: Induction Summation of Series

Let $P(n)$ be the following statement: $$\sum\limits^{n}_{i=0}r^i = \dfrac{1-r^{1+n}}{1-r}\text{ for all }n \in \mathbb{N}\text{.}$$ I am stuck at the base case: $$P(1):1 + r = ...
2
votes
2answers
36 views

Proof by Induction: $(1+x)^n \le 1+(2^n-1)x$

I have to prove the following by induction: $$(1+x)^n \le 1+(2^n-1)x$$ for $n \ge 1$ and $0 \le x \le 1$. I start by showing that it's true for $n=1$ and assume it is true for one $n$. ...
1
vote
2answers
53 views

How to simplify the formula for $n$th Fibonacci number when $n=2$?

When n is equal to 2 how do I simplify when the $n=2$ is put into the equation below (by the way I have to prove this formula by induction that when n= any number it will equal that number) ...
3
votes
3answers
76 views

Proof by induction: $n$th Fibonacci number is at most $ 2^n$

I'm trying to find the proof by induction of the following claim: For all $n\in\mathbb N$, $\operatorname{fibonacci}(n) \le 2^n$ My Proof: Base case: $n = 1$ $\operatorname{fibonacci}(1) \le 2^ 1$ ...
2
votes
2answers
85 views

Proof of equality $\sum_{k=0}^{m}k^n = \sum_{k=0}^{n}k!{m+1\choose k+1} \left\{^n_k \right\} $ by induction

I have a problem with following equality: $$\sum_{k=0}^{m}k^n = \sum_{k=0}^{n}k!{m+1\choose k+1} \left\{^n_k \right\} $$ And I would like to use induction in following way: Base: $$ m = n $$ And: $$ ...
0
votes
2answers
37 views

How to use the Comparison Test to investigate the convergence of $\sum (\ln n)/n^\alpha$?

Let $$\sum\limits_{n=1}^\infty \frac{\ln n}{n^\alpha}, \alpha\in\Bbb{R}$$ I need to investigate the convergence of this series. I've read that since the series is positive for all $n$ then it ...
0
votes
2answers
50 views

Mathematical Induction - Inequality

Does anyone have any idea on how to complete the inductive step? Thm: For all $n >= 0~~~~ 6^n + 4 > n^3$ Pf: by Induction     Let $P(n)$ be proposition that $~6^n + 4 ...
1
vote
2answers
43 views

Prove by induction a formula for $x_{k+1}=\frac{x_k}{x_k+2}$, $x_1=1$

I have a IT Maths exam coming up and I just can't figure out this question. Any help would be appreciated thanks. A sequence of integers $x_1,x_2,\dots,x_k,\dots$ is defined recursively by ...
0
votes
1answer
29 views

induction exercise doubt

the exercise states: Let $x_1 , ...,x_n$ be strictly positive numbers such that their product is equal to 1. Show then that $\sum_{k=1}^{n} {x_k} \ge n $, for every $n \ge 2$. My solution: for the ...
-4
votes
0answers
78 views

proof by mathematical induction that the total number of subsets of a set is $2^n$ [closed]

What is the proof by mathematical induction that the total number of subsets of a set is $2^n$?
0
votes
2answers
37 views

Proof in induction recrusive function

We've got the following function: $$f:N \rightarrow N$$ $$f(0) = 1$$ $$f(K+1) = (K+1)\times F(K)$$ How can I proof in induction the following: $$1\times f(1)+2\times f(2)+3\times f(3)+...+n\times ...
3
votes
1answer
72 views

Divisor function asymptotics

Define $\tau_{r}(n) = \sum_{d_1...d_r = n}1$. One exercise in a book on sieve theory asked for an elementary proof by induction of the fact that $$\sum_{n\le x}\tau_r(n) = \frac{1}{(r - 1)!}x(\ln ...
1
vote
1answer
52 views

problem: Applying Well-Ordering Principle to prove a fact

problem: Prove the fact using WOP: every amount of postage that can be assembled using only 10 cent and 15 cent stamps is divisible by 5. The problem provides a template for this proof and asks that ...
1
vote
2answers
31 views

Use induction to prove trignometric identity with imaginary number

Prove by induction that if $i^2 = -1 $, then for every integer $n >= 1$, $[\cos(x) + i\sin(x)]^n = \cos(nx) + i\sin(nx)$. My solution so far: 1. It can be easily shown that it is true for n = 1. ...
2
votes
1answer
68 views

Introductory Induction Proof

I am in currently in a discrete mathematics class, and I've done well on every problem I've encountered. Unfortunately, I find myself weak at some of the seemingly straight forward induction problems. ...
0
votes
6answers
110 views

How to prove $\tan^{-1}(n+1)-\tan^{-1}(n-1)=\tan^{-1}\big(\frac{2}{n^2}\big)$?

Prove $$\tan^{-1}(n+1)-\tan^{-1}(n-1)=\tan^{-1}\big(\frac{2}{n^2}\big)$$ for $n \ge 1$ If I use mathematical induction how do I manipulate the numbers to fit in the induction hypothesis? Is there ...
3
votes
2answers
56 views

Induction on GCD problem [duplicate]

This is a two part question Given $\gcd(a,b) = 1$ consider $$\gcd \left( \frac{a^n - b^n }{a-b}, a- b\right) $$ It appears that the value of this is always equal to $n$ or $1$. How to prove it? ...
0
votes
3answers
45 views

How to complete a proof by induction

I was trying my hand at proof by induction and got this exercise from the first chapter of Wissam Raji's "An introduction in elementary number theory". I have to prove by induction that $n< 3^n ...
3
votes
4answers
120 views

How to prove this $(n+1)^n < n^{n+1}$ for $\space n \ge 3$

I'm having some more trouble with induction I know how to prove this using $\ln$, but I need to use induction only. prove that: $(n+1)^n < n^{n+1}$ for any $ n\ge 3$
-1
votes
1answer
55 views

Inductive proof of a formula for Fibonacci numbers

May someone help me? I am trying to use induction to prove that the formula for finding the $n$-th term of the Fibonacci sequence is: ...
7
votes
5answers
77 views

prove by induction $7 \mid 3^{3^n}+8$

Okay so ive been trying to prove this for about 5 hours... really need salvation from the geniouses around here. prove by induction $7\mid 3^{3^n}+8$ i really need some directions on what to do ...
2
votes
1answer
19 views

Clarification regarding the Josephus problem in Concrete Mathematics (Knuth, et al)

In page 9 of Concrete Mathematics, regarding the Josephus Problem, they state that "each person's number has been doubled then decreased by 1". $J(2n) = 2J(n) - 1$, for $n \ge 1$ I don't quite ...
0
votes
2answers
72 views

Prove that $(2n+1)+(2n+3)+\dots +(4n-1) = 3n^2$ by induction

Note: This is for self study, the book is Elementary analysis by Kenneth. A. Ross How to prove the following by mathematical induction, I am stuck
1
vote
2answers
67 views

Induction inequality on sum of reciprocals

I have to prove that: $\displaystyle\frac{1}{n}+\frac{1}{n+1}+...+\frac{1}{2n}\ge\frac{1}{2}$ for natural $n$ Checking for $n=1$ we have $\displaystyle 1+\frac{1}{2}=\frac{3}{2}\ge \frac{1}{2}$ ...
1
vote
1answer
26 views

Expanding Base 2B representation of an integer

Consider an integer$L$ written in Base 2B which digits $$a_n a_{n-1} a_{n-2} ... a_1 B$$ Where $a_i$ are arbitrary constants such that $9 \le a_i < 2B$. I am attempting to prove that the square ...
4
votes
2answers
109 views

Prove that $\sqrt{n} \le \sum_{k=1}^n \frac{1}{\sqrt{k}} \le 2 \sqrt{n} - 1$ is true for $n \in \mathbb{N}^{\ge 1}$

I'm trying to solve these induction exercises proposed by the department of mathematics of Oxford University. I don't know how to give a valid proof for the third one which says the following: ...