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

0
votes
3answers
47 views

Prove that $\sum \frac{1}{2^n} = 1- \frac{1}{2^n}$ [closed]

Prove that $$\Large\sum\limits_{k=1}^n \frac{1}{2^k} = 1 - \frac{1}{2^n}$$ for all $n$. I am apparent not good enough at algebra for this one.
-1
votes
0answers
24 views

Proof by Induction (Permutations)

Let A be a set with n elements. Let S(A) be the set of all permutation of A; that is, S(A) is the set of all bijective functions from A to A. prove by induction that S(A) contains n! elements.
5
votes
0answers
35 views

My first proof that uses the well-ordering principle (very simple number theory). Please mark/grade.

What do you think about my first proof that uses the well-ordering principle? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof ...
0
votes
2answers
19 views

Let $A_1, A_2, \ldots, A_n$ be sets (where $n \ge 2$). Suppose for any two sets $A_i$ and $A_j$ either $A_i \subseteq A_j$ or $A_j \subseteq A_i$

Let $A_1, A_2, \ldots, A_n$ be sets (where $n \ge 2$). Suppose for any two sets $A_i$ and $A_j$ either $A_i \subseteq A_j$ or $A_j \subseteq A_i$. Prove by induction that one of these $n$sets is a ...
1
vote
2answers
61 views

Prove by induction $1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{2^n} \ge 1 + \frac {n}{2}$

Prove by induction $1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \ldots + \frac{1}{2^n} \ge 1 + \frac {n}{2}$ I can't explain in words how the left hand side of the equation is achieved soI shall ...
0
votes
2answers
44 views

Proofs for $g(x)=e^{-1/x^2}$ when $x\neq0$, and $g(x)=0$ when $x=0$

Sorry for the non-descriptive title - the question is a bit long. I have $g(x)$ as in the title, and we proved previously that $g'(0)=0$ using L'Hôpital's rule. Now I must show by induction that ...
1
vote
4answers
45 views

proof by induction: sum of binomial coefficients

Question: Prove that the sum of the binomial coefficients for the nth power of $(x + y)$ is $2^n$. i.e. the sum of the numbers in the $(n + 1)^{st}$ row of Pascal’s Triangle is $2^n$ i.e. prove ...
1
vote
1answer
30 views

Binomial Coefficient Recusions

Let m and j be non-negative integers. Define $S^{0}_{m} = 1$ and: $ S^{j}_{m} = \displaystyle\sum\limits_{i=1}^{m} S_{i}^{j-1}$ Show via induction: $ S_{m}^{j} = {m+j-1 \choose j} $ I can ...
2
votes
3answers
60 views

Mathematical induction proof that $8$ divides $3^{2n} - 1$

I'm struggling with this question: prove the following using simple mathematical induction. $$ 8 \mid (3^{2k} - 1) $$ What I've got so far is: $$ 3^{2k+2} - 1 = 3^{2k} \cdot 3^{2} - 1 $$ From here, ...
0
votes
2answers
41 views

Inductive proof and summation

The problem asks me to prove by induction that: $$\sum_{i=1}^n i^3 = \frac{n^2(n+1)^2}{4}$$ I've worked through it at least half a dozen times, checked my math fastidiously, can't seem to figure it ...
0
votes
2answers
30 views

Induction question help.

Let $x$ and $y$ belong to a commutative ring $R$ with prime characteristic $p$. Show that, for all positive integers $n$ $$ (( x + y )^p)^n = (x^p)^n + (y^p)^n $$ I hope you can can understand ...
3
votes
1answer
24 views

$a^{(m+n)}_{ij} \geq a^{(m)}_{ik}a^{(n)}_{kl}$ for non-negative Matrix $A$

Let $A$ be a non-negative infinite Matrix (all entries $\geq 0$). $a_{ij}^{(n)}$ denotes the $ij$-th entry of $A^n$. Does the following inequality hold: $a^{(m+n)}_{ij} \geq ...
2
votes
1answer
38 views

Help with induction proof for formula connecting Pascal's Triangle with Fibonacci Numbers

I am in the middle of writing my own math's paper on the topic of Pascal's Triangle. During the investigation I have came up with a formula for counting elements of Fibonacci Sequence using the ...
0
votes
1answer
26 views

Inductive Proof Recursive Definition

Using this recursive Definition: $$a_{n} = \left\{\begin{matrix} 4 & n=1\\ a_{n-1}+4n-5 & n \geq 2 \end{matrix}\right.$$ I somehow have to prove using induction $$a_{n} = 2n^{2} - ...
0
votes
1answer
35 views

Fibonacci Proof with Induction [duplicate]

$$f(n) = \left\{\begin{matrix} 0 & n=1\\ 1 & n=2\\ f_{n-1} + f_{n-2} & n\geqslant 2\end{matrix}\right.$$ How can I prove by induction that $$f_{n} \geq \left ( 1.5 \right )^{n-1}$$ ...
2
votes
2answers
45 views

Fibonacci Proof Using Induction

$$f(n) = \left\{\begin{matrix} 0 & n=1\\ 1 & n=2\\ f_{n-1} + f_{n-2} & n\geqslant 2\end{matrix}\right.$$ How can I prove by induction that $$f_{n} \leq \left ( \frac{1+\sqrt{5}}{2} ...
2
votes
1answer
49 views

Fibonacci proof by induction

I have fibonacci numbers defined as such: $$ f(n) = f(n-1) + f(n-2)$$with$$ f(0) = 0 $$$$f(1) = 1$$ I have to prove that $$ F(n) \geq 1.5^{n-1}, n \geq 6$$ Base Case: $$ f(6) = 8 \geq (1.5)^5 ...
0
votes
3answers
32 views

Divisibility proof by induction.

$ 169$ | $3^{3n+3}-26n-27$ ? Fulfilled for $n=0$. Induction to $n+1$: An integer $x$ exists so that $ 169x= 3^{3n+6}-26n-27-26$ $ 169x= 27*3^{3n+3}-26n-27-26$ $ 169x= 26*3^{3n+3}+3^{3n+3}-26n-27-26$ ...
0
votes
3answers
31 views

Induction summation proof

Don't want a full answer but can somebody help me in the right direction with this problem. Have to prove using induction $$\forall n \geqslant 2: \sum_{i=1}^{n} \frac{4}{5^{i}} < 1$$
0
votes
0answers
16 views

Structural induction question?

The question is: Give recursive definition of a set "S" of all binary strings starting with a 1. Do the three steps: base, recursion, and restriction So far, I have: base: empty string recursion: ...
2
votes
0answers
38 views

My first proof employing strong induction / complete induction (very simple number theory). Please mark/grade.

What do you think about my first proof employing strong induction? What mark/grade would you give me? Theorem Every natural number greater than 1 is a product of one or more primes. Proof First, ...
0
votes
1answer
27 views

Composition of linear maps and induction

With DonAntonio's help Composition of linear maps. I managed to find $t^4 = t^2 +4(t^2- id)$ , $t^6 = t^2 + 4(4+1) (t^2 -id)$ and $t^8 = t^2 + 4 ( 1+ 4 +4^2)(t^2 -id) $ So now I want to prove it ...
17
votes
3answers
664 views

My first induction proof (very simple number theory). Please mark/grade.

What do you think about my first induction proof? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof First, introducing a predicate ...
1
vote
1answer
82 views

Can't find an identy for proving that $ \sum_{k=0}^{i+1} \binom {i+1} k=2^{i+1}$ [duplicate]

$$ \sum_{k=0}^{i+1} \binom {i+1} k$$ I can't find an identity for this summation :( To clarify I'm trying to prove using induction that this sum is equal to $2^{i+1}$, I have my basis and ...
0
votes
1answer
17 views

Prove that all elements in the set T is divisible by 3 using structural induction.

Let T be the set defined recursively as follows: (1) (0,3) $\in$ T (2) If (x, y) $\in$ T, then (x + 2, y - 1) $\in$ T and (x - 3, y) $\in$ T. (3) Every element of T can be obtained from (1) by ...
1
vote
0answers
43 views

Proof by induction on contraction mapping?

Let $k:[0,1] \times [0,1] \to \mathbb{R}$ be continous, and $x(t) = \int_0^t k(t,s)x(s)ds$ for $0 \leq t \leq 1$. Not let $Tx(t) = \int_0^t k(t,s)x(s)ds$ and suppose $sup_{0 \leq t, s \leq 1}|k(t,s)|= ...
0
votes
2answers
49 views

Proving by mathematical induction

Let $d \in N $ be an odd integer. Prove by induction that: $\forall k \in N$ , $d^k$ = 1 (mod 2). How do I begin this question? I have a hard time understanding what to do for the inductive step. ...
1
vote
9answers
288 views

How to prove for each positive integer $n$, the sum of the first $n$ odd positive integers is $n^2$?

I'm new to induction so please bear with me. How can I prove using induction that, for each positive integer $n$, the sum of the first $n$ odd positive integers is $n^2$? I think $9$ can be an ...
0
votes
0answers
42 views

Prove $F_{n+2} \ge x^n$ by induction where $x = (1 + \sqrt{5})/2$

Base Case: $n = 1$: $F_3 \ge x^1$ translates to $3 \ge 1.6$, so the base case holds. Induction Hypothesis: Assume the statement is true for all $n$ such that 40 \le n \le k$. We will prove this ...
0
votes
0answers
27 views

How to use two types different forms of induction to prove stamp problem?

For this problem I have to prove using two different types of induction to show that using only 3 cent stamps and 5 cent stamps, any postage amount 8 cents or greater can be formed. Using the two ...
0
votes
0answers
33 views

Proving this property of a tournament graph by induction?

I am working on practicing proofs by induction. Can you please take a look at the proof below and tell me if I proved it correctly? I am particularly worried about the inductive step. Definition ...
0
votes
1answer
28 views

How can I prove prime factorization theorem by induction?

The prime factorization including both existence and uniqueness. I have totally no idea about this problem except the basecase. In this problem we only consider number greater or equal to 2. So the ...
1
vote
4answers
73 views

prove that a power of odd number is always odd by induction.

The problem has confused me for like half hour. An integer is odd if it can be written as d = 2m+1. Use induction to prove that the ${d^n}$ = 1 (mod 2) by induction, the basecase is pretty simple , ...
0
votes
1answer
45 views

Cayley's formula for the number of trees(Recursion)

I'm trying to understand the proof by recurcion and induction for the Cayley's formula for the number of trees.While I'm trying to understand it there are some things that I don't get at all. -It ...
1
vote
5answers
116 views

How to prove that $n^5 - n$ is a multiple of $5$? [duplicate]

Hello I'm new to induction so please bare with me. For this problem I have to use induction to prove: For every integer $n\geq 1$, the number $n^5 − n$ is a multiple of $5$. Can someone please help me ...
1
vote
1answer
39 views

How would I solve this mathematical induction proof? I am stuck after the first part of the induction.

$$1 + 5 + 5^2 + \ldots + 5^n = \frac{5^{n+1}-1}{4}$$ Basis case $n= 0$: $1^0 = 1 \;\;\;\;\;\;\;\;\;\;\;\; \frac{5^{1+1}-1}{4}=1$ Assume true for $n=k$: $$1 + 5 + 5^2 + \ldots + 5^k = ...
0
votes
3answers
46 views

proving golden ration with induction

If $\displaystyle a=\frac{1+\sqrt{5}}{2}$ and $\displaystyle b=\frac{1-\sqrt{5}}{2}$, prove that $\displaystyle f_n=\frac{a^n-b^n}{\sqrt{5}}$ for all $n\in\mathbb{P}$ Would we start with a base case ...
1
vote
2answers
40 views

Proving an inequality using induction

Use induction to prove the following: $\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{2^n}\geq1+\frac{n}{2}$ What would the base case be? Would it still be $n=0$ so ...
1
vote
4answers
53 views

Proof by induction

Prove that the inequality $n^2\geq n$ holds for every integer. With induction, I believe we would start with the base case, that is $n=0$ $n=0$ $0^2 \geq 0$, which is true. Then would I start with ...
3
votes
2answers
53 views

Help finishing proof via induction for a summation

So I have to prove the following equation using induction for n >= 2: $$ \sum\limits_{i=1}^n 4/5^i < 1 $$ However the question asks me to prove something stronger such as this: $$ ...
0
votes
2answers
40 views

What is the easiest way to prove by induction?

Is there any easy way to do this? I get the basic step.. where you prove it for some number.. but I don't get the induction step. Do you literally take the given equation that you just proved with ...
1
vote
4answers
43 views

Principle of mathematical induction problem

Prove the inequality $4^{2n}>15n$ For $n = 1$, $4^{2\cdot1}=16>15\cdot1$ Let us assume it is true for $n=k$ $4^{2k}>15k$
2
votes
1answer
47 views

When is there an $m$ that divides $u^{an+b}+v^{cn+d}$ for all $n$

This is a generalization of Prove by induction? which asks how to prove that $73$ divides $8^{n+2}+9^{2n+1} $for all $n$. Here is my generalization: Find conditions on positive integers $u, a, v, c$ ...
1
vote
1answer
20 views

Is this divisibility proof by induction correct/sufficient?

To show: 13 | $4^{2n+1}+3^{n+2}$ I used induction beginning successfully with n=0 (or n=1), then making the step to n+1: An x exists so that $13x = 4^{2n+3}+3^{n+3}$ $13x = 16*4^{2n+1}+3*3^{n+2}$ ...
0
votes
6answers
64 views

Prove by induction?

The problem asks to prove $8^{(n+2)}+9^{(2n+1)}$ is divisible by 73 Proof by induction: we look at base case $n=1$ => which gives us $1241$ which is divisible by $73$; now for $n+k$ we know that ...
1
vote
1answer
55 views

Proof by induction: $2^n > n$

Base is $2^1 > 1$. Now we assume $2^n > n$ and try to obtain $2^{n+1} > (n+1)$. If I can use $2^n > 1$, I could just add that to $2^n > n$ and get $2^{n+1} > (n+1)$ but I don't ...
2
votes
1answer
103 views

Prove by induction on $n$ that any set of $n$ reals is bounded

Prove by induction on $n$ that any set of $n$ reals is bounded Working: I approached the problem by splitting it into three cases and proving each case, it seems a bit tedious to me how I did it, so ...
1
vote
0answers
109 views

Can I use Strong Induction to prove graph theory? - Hamilton Path/Tournament Graphs

I am working on the below proof. I am still new to proves so I am wondering if you guys can answer the following questions: 1) Did I use the inductive hypothesis correctly here? (By the inductive ...
-1
votes
0answers
41 views

What is wrong with this induction proof for a closed form recursive function?

I need some help, I can't seem to find What is wrong in this proof, yet I'm not getting what I need. Anyone know? Prove by induction $2(S(2^{k-1})) + 2^k = 2(2^{k-1})k +2^k$, given that: $S(2^0 ) = ...
-5
votes
1answer
56 views

PRove using Principle of Mathematical Induction [closed]

Prove that $\left(3 + \sqrt{5} \right)^n + \left(3 - \sqrt{5}\right)^n$