Use mathematical induction to prove that an operation always leads to 1 or a loop

Question

Hello! I have a question: Use mathematical induction to prove that the operation of summing the squares of the digits always leads either to 1 or the single loop (4, 16, 37, 58, 89, 145, 42, 20, 4). I tried to use a specific example (n>3) but my teacher told me to be more broad. This is what I have so far:

n=number

d=# of digits in n

Base case: For n = 1, the sum of all the (digits squared) is equal to 1.

Inductive step: Assume that the statement above is true for all positive integers less than n. We will prove that it is also true for n.

Let n be a positive integer and let d1, d2, ..., dx be the digits of n, where x is the number of digits in n. Then the sum of all the (digits squared) of n is equal to:

(digit1^2)+(digit2^2)+(digit3^2)...(digitx^2)

According to the inductive step, this expression will either lead to 1 or to a loop.

Therefore, the statement holds for all positive integers n by mathematical induction.

I'm gonna be honest, I don't think my answer makes much sense. I'm trying to avoid using calculus, but I feel like I need to use logarithms. Thoughts?

Thank you so much!

Answer 1

1, 2, ,9

10, 11, 12, ,99

100, 101, 102, ...999

1000, 1001, 1002 . . .,9999

10000, 10001, 10002, 99999 . . .

.....;.... . ..

Clear that we have variable by quantity numbers loops, starting from 1

Answer 2

As Doug said, induction is not necessary, but here is a proof that does use induction.

For a natural number n, let s(n) be the sum of squares of its digits.

For example, s(12) = 5.

You are to deal with sequences

{n, s(n), s(s(n)), s(s(s(n))), ... }

denoted as

{s⁰(n), s1(n), s²(n), s³(n), ...}

or simply

{..., sⁱ(n), ...}.

You are to prove that for any natural number n there exist natural numbers i and j, so that

i ≠ j and sⁱ(n) = s^j(n).

Notice that in this formulation neither n = 0, nor n = 1 are a special case.

The proof is based on the observation that s(999) = 243.

If you start with any number n having at most three digits,

(and since each digit is at most 9), then s(n) ≤ 243.

This implies that s(n) is again at most a three digit number.

So all the values in {..., sⁱ(n), ...} are coming from the set of 244 possibilities,

and for any sequence longer than 244 there must be repetitions.

On the other hand, if you start with n > 999 then s(n) < n.

That implies that the sequence will be decreasing till the reaches a three digit number,

at which point the above argument applies.

To be more formal you need to prove a couple lemmas.

Lemma 1: If n > 999 then s(n) < n.

Lemma 2: For any natural number k,

if {a₀, a₁, ...} is an infinite sequence of numbers in the range [0, k],

then there are i ≠ j satisfying a_i = a_j.

For Lemma 1 you can use logarithms and calculus.

For Lemma 2, although obvious, you have an opportunity to use induction like this.

Basis step: If k = 0, then the sequence is {0, 0, ...}, and the lemma is satisfied with

i = 0, j = 1.

Induction step: Assume the lemma true for k and assume any infinite sequence {a₀, a₁, ...}

whose elements are in the range [0, k+1].

There are three cases:

Case 1: There is no a_i = k+1.

Then the sequence is in the range [0,k], and satisfies the Lemma by induction hypothesis.

Case 2: There is exactly one a_i = k+1.

Then the sequence {a_i+1, a_i+2, ...} is in the range [0, k], and hence satisfies the Lemma by induction hypothesis.

Case 3: There are at least two distinct i and j satisfying a_i = k+1 and a_j = k+1.

Those two i and i then satisfy the lemma.

PROOF OF LEMMA 1:

Let d be the number of decimal digits in n.

(For example, if n = 7312, then d = 4)

Then n = a10^d-1 + r

where 1 ≤ a ≤ 9 and r is the value of the remaining digits.

Thus n ≥ 10^d-1 .

At the same time s(n) ≤ 9²d (because each of the d digits can be at most 9).

The lemma will be proven if we can show

9²d < 10^d-1 .

We prove that by induction on d.

Basis step: d = 4 (Recall that n > 999)

9²×4 < 10³

which completes the basis step.

Induction step: Assume the lemma true for d and we will prove it for d+1.

9²(d+1) = 9²d + 81 (by algebra)

< 10^d-1 + 81 (by induction hypothesis)

< 10^d-1 + 10^d-1 (because d > 4)

= 2×10^d-1

< 10×10^d-1

= 10^d

This proves the lemma.

PROOF OF THEOREM:

The proof is by induction on the size of n.

Basis step: n < 1000

As n has at most 3 digits, s(n) ≤ 3×9² < 1000

Consequently (if you like by induction) each sⁱ(n) is in the range [0, 999].

Therefore by Lemma 2 there exist i and j satisfying the theorem.

Induction step: Let n > 999 and assume the theorem true for any natural number k, such that 0 < k < n;

then prove it for n.

By Lemma 1 s(n) < n.

Therefore by induction hypothesis s(n) satisfies the theorem, and the sequence

{s¹(n), s²(n), ... } yields indices i ≠ j so that sⁱ(n) = s^j(n).

These indices then also work for

{s⁰(n), s¹(n), s²(n), ... },

which proves the induction step and the theorem.

Answer 3

Sorry, I don't think this question is well posed. A sum yields a value, not a loop. Perhaps you mean that the sequence of output values will repeat in some way. I don't think that's correct. Let s(n) be the sum of the squares of the digits of n. Then the sequence (n,s(n)) is (1, 1), (2, 4), (3, 9), (4, 16), (5, 25), (6, 36), (7, 49), (8, 64), (9, 81), (10, 1), (11, 2), (12, 5), (13, 10), (14, 17), (15, 26), (16, 37), (17, 50), (18, 65), (19, 82), (20, 4), (21, 5), (22, 8), (23, 13), (24, 20), (25, 29), (26, 40), (27, 53), (28, 68), (29, 85), (30, 9), (31, 10), (32, 13), (33, 18), (34, 25), (35, 34), (36, 45), (37, 58), (38, 73), (39, 90), (40, 16), (41, 17), (42, 20), (43, 25), (44, 32), (45, 41), (46, 52), (47, 65), (48, 80), (49, 97), (50, 25), (51, 26), (52, 29), (53, 34), (54, 41), (55, 50), (56, 61), (57, 74), (58, 89), (59, 106), (60, 36), (61, 37), (62, 40), (63, 45), (64, 52), (65, 61), (66, 72), (67, 85), (68, 100), (69, 117), (70, 49), (71, 50), (72, 53), (73, 58), (74, 65), (75, 74), (76, 85), (77, 98), (78, 113), (79, 130), (80, 64), (81, 65), (82, 68), (83, 73), (84, 80), (85, 89), (86, 100), (87, 113), (88, 128), (89, 145), (90, 81), (91, 82), (92, 85), (93, 90), (94, 97), (95, 106), (96, 117), (97, 130), (98, 145), ...

import numpy as np

def digits(num): # https://math.stackexchange.com/questions/2952462/finding-the-leading-digits-in-any-number

s = str(num)

return np.sum([int(j)**2 for j in s])

print([(i,digits(i)) for i in range(99)])